A formalism is presented which predicts the influence of laterally heterogeneous slip (for instance, induced by nanoscopic air bubbles) on the shift of the resonance frequency and bandwidth of quartz crystal resonators immersed in liquids. The lateral heterogeneities are decomposed into their Fourier components. The distribution of slip lengths provides a boundary condition, giving rise to a small, secondary flow field. The mean stress exerted by this secondary field induces a shift in resonance frequency and bandwidth. If the slip length is much smaller than the penetration depth of the shear waves and smaller than the lateral correlation length, one finds that the effects of the heterogeneities scale as n(3/2), with n being the overtone order. The frequency, f, and half-band-half-width, F, decrease by the same amount. These calculations match experimental results obtained with a gold-coated resonator in contact with various hydrophilic liquids.