We report on a combined experimental and theoretical study of spin-dependent relaxation processes in the electron system of an iron film on Cu(100). Spin-, time-, energy-, and angle-resolved two-photon photemission shows a strong characteristic dependence of the lifetime of photoexcited electrons on their spin and energy. Ab initio calculations as well as many-body treatment corroborate that the observed properties are determined by relaxation processes involving magnon emission. Thereby we demonstrate that magnon emission by hot electrons occurs on the femtosecond time scale and thus provides a significant source of ultrafast spin-flip processes. Furthermore, engineering of the magnon spectrum paves the way for tuning the dynamic properties of magnetic materials.