Irradiation of a Ru(001) surface covered with CO using intense femtosecond laser pulses (800 nm, 130 fs) leads to desorption of CO with a nonlinear dependence of the yield on the absorbed fluence (100-380 J/mē). Two-pulse correlation measurements reveal a response time of 20 ps (FWHM). The lack of an isotope effect together with the strong rise of the phonon temperature (2500 K) and the specific electronic structure of the adsorbate-substrate system strongly indicate that coupling to phonons is dominant. The experimental findings can be well reproduced within a friction-coupled heat bath model. Yet, pronounced dynamical cooling in desorption, found in the fluence-dependence of the translational energy, and non-Arrhenius behaviour of the desorption probability reflect pronounced deviations from thermal equilibrium during desorption taking place on such a short time scale.