Comment by orthoxerox

The "-sha" pattern is relatively consistent: Pavel-Pasha, Mikhail-Misha, Natalya-Natasha, Nikolay-Nikolasha, Alexey-Alyosha, Mariya-Masha, Ilya-Ilyusha.

So, Aleksandr-Aleksasha. The dropping of "Alek" is the only inconsistent part, on par with Agrippina-Agrusha-Grusha.