The role of surface collective excitations in the electron relaxation in small metal particles is studied. It is shown that the dynamically screened electron-electron interaction in a nanoparticle contains a size-dependent correction induced by the surface. This leads to new channels of quasiparticle scattering accompanied by the emission of surface collective excitations. In noble-metal particles, the dipole collective excitations (surface plasmons) mediate a resonant scattering of d-holes to the conduction band. The role of this effect in the ultrafast optical dynamics of small nanoparticles is studied. With decreasing nanoparticle size, it leads to a drastic change in the differential absorption lineshape and a strong frequency dependence of the relaxation near the surface plasmon resonance. The experimental implications of these results in ultrafast pump-probe spectroscopy are addressed. We also discuss the size-dependence of conduction electron scattering rates.