Evolutionary structure searches are used to predict stable phases with unique stoichiometries in the hydrogen-rich region of the magnesium/hydrogen phase diagram under pressure. MgH$_4$, MgH$_{12}$ and MgH$_{16}$ are found to be thermodynamically stable with respect to decomposition into MgH$_2$ and H$_2$ near 100 GPa, and all lie on the convex hull by 200 GPa. MgH$_4$ contains two H$^-$ anions and one H$_2$ molecule per Mg$^{2+}$ cation, whereas the hydrogenic sublattices of MgH$_{12}$ and MgH$_{16}$ are composed solely of H$_2^{\delta -}$ molecules. The high-hydrogen content stoichiometries have a large density of states at the Fermi level, and the $T_c$ of MgH$_{12}$ at 140 GPa is calculated to be nearly three times greater than that of the classic hydride, MgH$_2$, at 180 GPa.
