We present theoretical and experimental studies of the decoherence of hyperfine ground-state superpositions due to elastic Rayleigh scattering of light off-resonant with higher lying excited states. We demonstrate that under appropriate conditions, elastic Rayleigh scattering can be the dominant source of decoherence, contrary to previous discussions in the literature. We show that the elastic-scattering decoherence rate of a two-level system is given by the square of the difference between the elastic-scattering textit{amplitudes} for the two levels, and that for certain detunings of the light, the amplitudes can interfere constructively even when the elastic scattering textit{rates} from the two levels are equal. We confirm this prediction through calculations and measurements of the total decoherence rate for a superposition of the valence electron spin levels in the ground state of $^9$Be$^+$ in a 4.5 T magnetic field.