We report on first measurements of low-mass electron pairs in Pb-Au collisions at the lower SPS beam energy of 40 AGeV. The pair yield integrated over the range of invariant masses 0.2<m<1 GeV/c^2 is enhanced by a factor of 5.1+-1.3(stat)+-1.0/1.5(syst data/decays) over the expectation from neutral meson decays, more than previously observed at the higher energy of 158 AGeV. The results are discussed with reference to model calculations based on pi+ pi- -> e+ e- annihilation with a modified rho-propagator. They may be linked to chiral symmetry restoration and support the notion that the in-medium modifications of the rho are more driven by baryon density than by temperature.