MnO2 is attracting considerable interest in the context of rechargeable batteries, supercapacitors, and Li-O-2 battery applications. This work investigates the electrochemical properties of hollandite alpha-MnO2 using density functional theory with Hubbard U corrections (DFT+U). The favorable insertion sites for Li-ion and Na-ion insertion are determined, and we find good agreement with measured experimental voltages. By explicit calculation of the phonons we suggest multiple insertion sites are accessible in the dilute limit. Significant structural changes in alpha-(Li,Na)(x)MnO2 during ion insertion are demonstrated by determining the low energy structures. The significant distortions to the unit cell and Mn coordination are likely to be active in causing the observed degradation of alpha-MnO2 with cycling. The presence of Li2O in the structure reduces these distortions significantly and is the probable cause for the good experimental cycling stability of alpha-[0.143Li(2)O]-MnO2. However, the presence of Na2O is less effective in reducing the distortion of the Na-ion intercalated form. We also find a distinct change in the favored Li-ion insertion site, not identified in previous studies, for lithiation of alpha-LixMnO2 at x > 0.5. The migration barriers for both Li-ions and Na-ions increase from <0.3 eV in the dilute limit to >0.48 eV for alpha-(Li,Na)(0.75)MnO2. Finally, the electronic density of states in alpha-MnO2 with the incorporation of Li2O has the character of a full metal, not a half metal as was suggested in previous work. This may be key to its good performance as a catalyst in Li-O-2 batteries.