The Kelvin-Helmholtz Instability (KHI) has been observed in the solar atmosphere. Ion-neutral collisions may play a relevant role for the growth rate and evolution of the KHI in solar partially ionized plasmas as in, e.g., solar prominences. Here, we investigate the linear phase of the KHI at an interface between two partially ionized magnetized plasmas in the presence of a shear flow. The effects of ion-neutral collisions and compressibility are included in the analysis. We obtain the dispersion relation of the linear modes and perform parametric studies of the unstable solutions. We find that in the incompressible case the KHI is present for any velocity shear regardless the value of the collision frequency. In the compressible case, the domain of instability depends strongly on the plasma parameters, specially the collision frequency and the density contrast. For high collision frequencies and low density contrasts the KHI is present for super-Alfvenic velocity shear only. For high density contrasts the threshold velocity shear can be reduced to sub-Alfvenic values. For the particular case of turbulent plumes in prominences, we conclude that sub-Alfvenic flow velocities can trigger the KHI thanks to the ion-neutral coupling.