We identify the mechanism of energy dissipation relevant to spin-sensitive nanomechanics including the recently introduced magnetic exchange force microscopy, where oscillating magnetic tips approach surface atomic spins. The tip-surface exchange couples spin and atom coordinates, leading to a spin-phonon problem with Caldeira-Leggett type dissipation. In the overdamped regime, that can lead to a hysteretic flip of the local spin with a large spin-dependent dissipation, even down to the very low experimental tip oscillation frequencies, describing recent observations for Fe tips on NiO. A phase transition to an underdamped regime with dramatic drop of magnetic tip dissipation should in principle be possible by tuning tip-surface distance.