With respect to how I come up with lore, it usually comes to me in my dreams. At least the initial design does, but sometimes it can be quite extensive. I will usually borrow some small ideas from TV shows I have watched. As for how in depth it should be, that depends on what kind of game you want to create. For example, my game focuses much more on the characters (their personalities, lives, growth, etc.) than it does on the region itself. To that end, I want to create an interesting, diverse region, but I only need it so much as to allow for my characters to live in it and for the story to unfold. Therefore I do not need to build it too intensely, but rather as much that it feels alive and concrete, that my game is only one part of the region's overall history.
I find it best to first get a gist of the story you want, then create the region. Define its boundaries, its laws, at least a simple history, and so on. Keep these in mind when you actually write out the story. I think going as far back as the formation of the region itself is a little over the top. Granted, depending on your story, you may need exactly that.
I'd like to add that legendary-centric stories feel lackluster and overdone to me. That doesn't mean I find it bad for them to appear in the story; in fact my own game involves them quite extensively. They just are not the overall focus of the story.