One of the most powerful cosmological datasets when it comes to constraining neutrino masses is represented by galaxy power spectrum measurements, $P_{gg}(k)$. The constraining power of $P_{gg}(k)$ is however severely limited by uncertainties in the modeling of the scale-dependent galaxy bias $b(k)$. In this Letter we present a new method to constrain $b(k)$ by using the cross-correlation between the Cosmic Microwave Background (CMB) lensing signal and galaxy maps ($C_\ell^{\rm \kappa g}$) using a simple but theoretically well-motivated parametrization for $b(k)$. We apply the method using $C_\ell^{\rm \kappa g}$ measured by cross-correlating Planck lensing maps and the Baryon Oscillation Spectroscopic Survey (BOSS) Data Release 11 (DR11) CMASS galaxy sample, and $P_{gg}(k)$ measured from the BOSS DR12 CMASS sample. We detect a non-zero scale-dependence at moderate significance, which suggests that a proper modeling of $b(k)$ is necessary in order to reduce the impact of non-linearities and minimize the corresponding systematics. The accomplished increase in constraining power of $P_{gg}(k)$ is demonstrated by determining a 95% C.L. upper bound on the sum of the three active neutrino masses $M_{\nu}$ of $M_{\nu}<0.19\, {\rm eV}$. This limit represents a significant improvement over previous bounds with comparable datasets. Our method will prove especially powerful and important as future large-scale structure surveys will overlap more significantly with the CMB lensing kernel providing a large cross-correlation signal.