I don't know if these count as Russian songs but i like them anyway.
Okonchen Put' (End of the Road) by Yul Brynner, one of his gyspy songs
http://www.youtube.com/watch?v=426hAQaQAKMThe Hills of Manchuria by Maxim Troshin, music by I. Shatrov
http://www.youtube.com/watch?v=fWDgs34wilkLegend (Legenda in Russian) but in English more searches come up with Crown of Roses. I don't remember who it was written by but it was set to music by Tchaikovsky. It's beautiful and haunting. A lot of searches came up on Youtube but i have no speakers so i don't know if they're any good.
The Crown of Roses (or, The Legend)
When Jesus Christ was yet a child
He had a garden small and wild,
Wherein he cherished roses fair,
And wove them into garlands there.
Now once, as summertime drew nigh,
There came a troop of children by,
And seeing roses on the tree,
With shouts they plucked them merrily.
"Do you bind roses in your hair?"
They cried, in scorn, to Jesus there.
The Boy said humbly, "Take, I pray,
All but the naked thorns away."
Then of the thorns they made a crown,
And with rough fingers pressed it down,
'Til on His forehead, fair and young,
Red drops of blood, like roses sprung.