Speaking from experience, looking around an actual mountain to find a passage is no where near easy as when you are that close, you can't actually see much of it. And with sufficient height it might well be impossible to actually see the top of mountains while on ground level.
As for explaining the magical map... TES never does. You just have a self-drawing map, automatically in your possession. I don't think there was ever a story reason for any of them in any TES game.
I never thought they were "magical" in any way. I just assumed your character marked them in kind of in the background of everything.
This is a full 3D map. So yeah, it's definitely has to be magical. And yeah, it probably doesn't NEED an explanation, as you could just make it up, but I just don't like it personally. I still feel it doesn't fit all that well.
As for people who would find it too hard to do without "Google maps", I say get over it. I don't see why everything needs to be dumbed down because people don't want to explore, get lost, and be immersed in an open world game.