The ballet basically took two common characters found in Russian folklore, Koshchey the Deathless and the Firebird.
The villain of the ballet is Koshchey, who holds ten young princesses captive. The Russian tale "Koshchey the Deathless" tells of the hero, Ivan, who goes in search of the Princess he knew of from the lullabies his nurses sang to him. The compassion he has on a man being flogged (Bulat the Brave) results in Bulat accompanying him on a series of quests, basically doing everything for him, including freeing the Princess Vasilisa from Koshchey and finding his death, to kill it. The death itself is in an egg in a duck in a hare in a coffer under an oak on an island in the sea. In the ballet they simplified it to just being an egg he has to smash.
Koshchey is also found in the tale "Maria Morevna." Feminists would love this tale-Ivan only allows suitors to marry his sisters if his sisters consent (the suitors are all birds...?...but it's okay because they can all turn into men...), and then marries Maria Morevna, who is beautiful and powerful, can slay whole armies by herself, and has imprisoned Koshchey. In fact, it's sort of a role-reversed Bluebeard, because Ivan is forbidden to look into a certain closet; he does and ends up freeing Koshchey and has to go search for Maria Morevna. After many trials (including dying...thank goodness for the water of life) Ivan defeats Koshchey by smashing his head. Ironic how Koshchey the Deathless always ends up dead...
The Firebird is in different Russian tales-"The Firebird and Princess Vasilisa" is less related to the ballet plot. In this one, a hunter finds a feather of the Firebird, and is warned by his horse not to take it. He, of course, does, which again results in many impossible quests, in which he is aided-this time by the horse, whose loyalty wins his master a Princess in the end.
"Prince Ivan, the Firebird, and the Gray Wolf" (which is available to read on Surlalune) has the beginning sequence of the ballet plot-the Firebird is stealing apples from the King's orchard. Ivan's brothers try to keep watch but fall asleep. Ivan stays awake when it is his turn, and manages to grab the Firebird's tail, and is left with a feather, which he presents to his father. Once again, series of impossible tasks which the hero wins with the aid of a helper-this time a gray wolf who felt badly after tearing Ivan's horse to pieces. One of the tasks is to bring back the whole Firebird, and the wolf warns him to bring the bird but not touch the cage. I bet you can guess what happened next...other than that the Firebird doesn't really factor in the plot.
In "The Maiden Tsar" (interesting tale-the villain is an incestuous stepmother) the Firebird has a little more power, like she does in the ballet-she rescues Ivan from a Baba Yaga. Later on, the egg in the duck in the hare in the coffer in the oak in the ocean is seen again-this time the egg contains the Maiden Tsar's love, not Koshchey's death.
I don't know of any tales in which 10 maidens are all kept prisoner-I'm pretty sure that was thrown in there to give the corps de ballet something to do.
Images from here and by Ivan Bilibin