Small-scale dynamos (SSDs) are ubiquitous in a broad range of turbulent flows with large-scale shear, ranging from solar and galactic magnetism to accretion disks, cosmology, and structure formation. Using high-resolution direct numerical simulations, we show that in non-helically forced turbulence with zero mean magnetic field, large-scale shear supports SSD action, i.e., the dynamo growth rate increases with shear and shear enhances or even produces turbulence, which, in turn, further increases the growth rate. When the production rates of turbulent kinetic energy due to shear and forcing are comparable, we find scalings for the growth rate gamma of the SSD and the turbulent rms velocity u(rms) with shear rate S that are independent of the magnetic Prandtl number: gamma proportional to vertical bar S vertical bar and u(rms) proportional to vertical bar S vertical bar(2/3). For large fluid and magnetic Reynolds numbers, gamma, normalized by its shear-free value, depends only on shear. Having compensated for shear-induced effects on turbulent velocity, we find that the normalized growth rate of the SSD exhibits the scaling, (gamma) over tilde proportional to vertical bar S vertical bar(2/3), arising solely from the induction equation for a given velocity field.