We develop a many-body description of ultrafast electron dynamics in surface bands appropriate for studying relaxation of hot electrons and holes excited in the processes of one- and two-photon photoemission and inverse photoemission from surfaces. The description is based on the formalism for calculation of quasiparticle survival probabilities combined with self-consistent treatment of the electronic response of the system. We show that the calculation of survival amplitudes which carry information on the quasiparticle decay and decoherence can be conveniently mapped onto the problem of renormalization of quasiparticles by the interactions with bosonized excitations constituting the system heatbath. Applying this approach to the benchmark Cu(111) surface we are able to assess the regimes of preasymptotic non-Markovian quasiparticle dynamics in surface bands and locate transitions to the regime of exponential decay governed by the modified Fermi golden rule-type of transition rates. The general validity of these findings enables us to establish borderlines between different regimes of ultrafast electronic relaxation and on that basis to introduce a simple interpolation scheme for modeling of quasiparticle decay in the course of spectroscopic measurements.