Aims. In the first few minutes of a newborn neutron star's life the Hall effect and differential rotation may both be important. We demonstrate that these two ingredients are sufficient for generating a 'shear-Hall instability' and for studying its excitation conditions, growth rates, and characteristic magnetic field patterns. Methods. We numerically solve the induction equation in a spherical shell, with a kinematically prescribed differential rotation profile {\Omega}(s), where s is the cylindrical radius. The Hall term is linearized about an imposed uniform axial field. The linear stability of individual azimuthal modes, both axisymmetric and non-axisymmetric, is then investigated. Results. For the shear-Hall instability to occur, the axial field must be parallel to the rotation axis if {\Omega}(s) decreases outward, whereas if {\Omega}(s) increases outward it must be anti-parallel. The instability draws its energy from the differential rotation, and occurs on the short rotational timescale rather than on the much longer Hall timescale. It operates most efficiently if the Hall time is comparable to the diffusion time. Depending on the precise field strengths B0, either axisymmetric or non-axisymmetric modes may be the most unstable. Conclusions. Even if the differential rotation in newborn neutron stars is quenched within minutes, the shear-Hall instability may nevertheless amplify any seed magnetic fields by many orders of magnitude.