We proposed and analyzed a novel mechanism for long-range spin-spin interactions in diamond nanostructures. The interactions between electronic spins, associated with nitrogen-vacancy centers in diamond, were mediated by their coupling via strain to the vibrational mode of a diamond mechanical nanoresonator. That coupling resulted in phonon-mediated effective spin-spin interactions that could be used to generate squeezed states of a spin ensemble. We showed that spin dephasing and relaxation could be largely suppressed, which allowed for substantial spin squeezing under realistic experimental conditions. Our approach had implications for spin-ensemble magnetometry, as well as phonon-mediated quantum information processing with spin qubits.