Superfluid hydrodynamics affects the spin-evolution of mature neutron stars, and may be key to explaining timing irregularities such as pulsar glitches. However, most models for this phenomenon exclude the global instability required to trigger the event. In this paper we discuss a mechanism that may fill this gap. We establish that small scale inertial r-modes become unstable in a superfluid neutron star that exhibits a rotational lag, expected to build up due to vortex pinning as the star spins down. Somewhat counterintuitively, this instability arises due to the (under normal circumstances dissipative) vortex-mediated mutual friction. We explore the nature of the superfluid instability for a simple incompressible model, allowing for entrainment coupling between the two fluid components. Our results recover a previously discussed dynamical instability in systems where the two components are strongly coupled. In addition, we demonstrate for the first time that the system is secularly unstable (with a growth time that scales with the mutual friction) throughout much of parameter space. Interestingly, large scale r-modes are also affected by this new aspect of the instability. We analyse the damping effect of shear viscosity, which should be particularly efficient at small scales, arguing that it will not be sufficient to completely suppress the instability in astrophysical systems.