Coherent spin dynamics in the THz domain coupled to a coherent phonon is observed in the time-resolved second harmonic response of the Gd(0001) ferromagnetic metal surface. An LO phonon of 2.9 THz is excited by a transient charge displacement at the surface caused by resonant absorption of a fs laser pulse in the exchange-split surface state. This lattice vibration modulates the interlayer distance inducing a coherent variation of the exchange interaction between spins in adjacent layers. The resulting magnetization dynamics is considered as optical magnon wave packets coupled to the phonon.