The electron-phonon (e-p) coupling for the surface bands of Mo(112) has been studied by density functional theory (DFT). There are significant contributions from the surface phonon modes to the low frequency part of the phonon density of states and Eliashberg function, which results in enhanced e-p coupling at the surface and, consequently, an increase of the mass enhancement factor and the imaginary part of the self-energy. We suggest that the enhanced e-p coupling, together with anharmonic effects, scattering off impurities, as well as decay channels through adjacent bulk bands, leads to the increase of the linewidth of the electronic surface bands crossing the Fermi level observed in high resolution photoemission spectra of the Mo(112) surface.