This concept is used in Windaria and an early episode of Pokémon (Episode 20: "The Ghost of Maiden's Peak").
Did it come from a Japanese legend I'm not familiar with, did it come from the Windaria novel, or is it just a Kunihiko Yuyama thing?
Anime & Manga Stack Exchange is a question and answer site for anime and manga fans. It only takes a minute to sign up.Sign up to join this community
Stone legends are indeed pretty common just as TurkeyFried stated. Most of these are based on loyalty towards a person (most common in anime is waiting for a loved one).
It is said that the petrifaction version originates from Vietnam
Hòn Vọng Phu (Statue of Husband Waiting)
But nowadays in TV shows and such they give their own meaning to it and reasoning.
You can check this out for some more examples of this phenomena.