What gileonnen said - Snegurochka - though I would never have remembered the snow girl's name on my own. It is definitely a fairy tale of some sort - I can remember reading it from an old book of Russian fairy tales when I was little.

http://en.wikipedia.org/wiki/Snegurochka has a little more information. :) I never knew the version where she grew up to love a shepherd, though - just the version where she melted in the spring.