Going in, I suppose I'd try to remember that the earliest story telling may just have been someone lying to cover a mistake. And that a lot of old stories tend to feel universal or if not universal, tend to offer insight to a particular culture's fears, anxieties, and values.
I think with any myth or legend you need to at it's roots have a basic good story. Tragedy, battles, romance, etc. Something juicy that would allow it to be built upon and perpetuated at it's core. And that on top of that very basic story you have the culture. What kind of hero does this culture value. What kind of person is perceived as wicked or bad? What does it fear? What is considered good and valuable? Add centuries and they've been built upon, changed or adapted.
Maybe it started out as simple as someone saying "Here's what I think really happened to Beargun of Mount Mangosteen..." After he lost his throne in some really uninteresting way.
But maybe the story that person told was better, and people considered it. Ages passed, and it endured by being interesting. And by interesting I mean the same stuff I said above. Epic Battles, Some sort of horror, sex, treasure, etc. etc.
Rumors, stories made up in gossip, could all make a myth.
I'd also look to some of our own myths and legends for inspiration. For instance, a lot of creation myths are very similar. There's a lot of birth motifs as an example.
And that's probably because ancient people know birth as how new life comes into the world. Why shouldn't there be some fantastical birthing for the universe as they know it? And there's a whole lot more than that and I'm sure the internet could find some really interesting ones.
Lastly, and this is maybe just reiterating, these are oral traditions largely.
Myths and legends are born from people telling the same story over and over. And maybe someone keeps adding new parts. Making up something they thought was better. Forgetting parts. Accidentally mixing two stories up. Vilifying some parts and idolizing others based on the cultural values, exaggerating, ennobling, downplaying.
Variations are made by region.
And some stories die and some get passed down for millennia.
I don't know if that was too much or too little information, but I hope it helps! Much luck on your myth-building :)
