I'd say that one will respond to the other. An island chain that looks like a snake may immediately remind me of japanese creation myths and become incorporated that way but at the opposite end of the spectrum it would be easy to decide that these people are some variant of romans so I should use roman myths. The map gets slotted in around this.
The main thing is to use some sort of central point and move around that. The rest should grow organically even if the idea is simple.
My idea might be "war is hell" so my map turns to desert terrain (hell is hot, so is the desert). from there I could create a myth that drives my heros onwards... say, the ancestral race that they are descended from was big on personal sacrifice, the hero will never live up to that but cannot afford to give up. Then to tie it in the word was created by a fire-god or the like.
I suppose what I'm trying to say is that myths, maps and memorabilia should all join up. How you get there doesn't matter but don't be afraid to cast away a myth or map idea that may work better in some other setting.