Aprotic alkali metal-oxygen batteries are promising high specific energy alternatives to Li-ion batteries. Growth and dissolution of alkali metal oxides such as Li2O2 in Li-O2 batteries and NaO2 and KO2 in Na-O2 and K-O2 batteries, respectively, are central to the discharge and charge processes in these batteries. However, crystal growth and dissolution of the discharge products is poorly understood, especially in aprotic electrolytes. In this work, we chose the growth of NaO2 in Na-O2 batteries as a model system and show a strong correlation between the electrolyte salt concentration and the NaO2 crystal size. With a combination of experiments and theory, we argue that the correlation is a direct manifestation of the strong cation-anion interactions, leading to decreased crystal growth rate at high salt concentrations. Furthermore, we propose and experimentally demonstrate that cation-coordinating crown molecules are electrochemically stable electrolyte additives that weaken ion pairing and enhance discharge capacities in metal-oxygen batteries.