We present optical and near-infrared spectroscopy obtained at Keck, Very Large Telescope, and Gemini for a sample of 36 secure strong gravitational lens systems and 17 candidates identified as part of the Strong Lensing Legacy Survey. We combine these data with photometric and lensing measurements presented in the companion paper III and with lenses from the Sloan Lens Advanced Camera for Surveys and Lenses Structure and Dynamics surveys to investigate the cosmic evolution of the internal structure of massive early-type galaxies over half the age of the universe. This result is obtained by combining our measured dependencies of gamma ' on z, M sub(*), R sub(eff) with the evolution of the R sub(eff)-M sub(*) taken from the literature, and is broadly consistent with current models of the formation and evolution of massive early-type galaxies. Detailed quantitative comparisons of our results with theory will provide qualitatively new information on the detailed physical processes at work.