Here's the information we have on the Russian name "Sasha."
"Sasha" is a modern diminutive of "Aleksandr" and "Aleksandra." There are few examples of diminutives of these names in period, but we did find "Shashcha" from 1522. (1) We doubt that "Shashcha" would have been used earlier in period, since a survey of earlier names from Novgorod shows no diminutives of either name. (2) "Shashcha" would be appapropriate for a late-period Russian name, however.
In case you prefer to use an early name, you might like to know that "Oleksandra" is a more common spelling than "Aleksandra."
We hope this has been helpful, and that we can continue to assist you.
Talan Gwynek, Ivanor of Sighty Crag, Lindorm Eriksson, and Arval Benicouer contributed to this letter.
Academy of S. Gabriel
(1) Goldschmidt, Paul. "A Dictionary of Russian Personal Names."
(2) Baecklund, A. "Personal Names in Medieval Velikij Novgorod."
Correction by Aryanhwy, 25 Jun 2011: The report originally had the spelling "Sashcha", but the form found in Paul's "Dictionary" dated to 1522 is in fact "Shashcha".