Honestly, I imagine it would have to do with an adaptation to the environment. Yes, while they have one leg, they're also just about perfectly balanced with their symmetrical bodies, and are able to place themselves in heaps of garbage to escape the harsh winds. Whether or not their other traits were formed by this I don't know. Perhaps they're used to feeding on the blood of those giant rats.
As for the ones on the Black Omen, I'm very certain that Lavos's energy had a hand in their forms. Like the mutants you see in the junkyards, they've got a body akin to an hourglass, which would suggest some kind of relation. However, with the magical energy radiated and tapped into by the Black Omen from Lavos, it would only serve to empower, and in effect twist them, ever further from their roots.
So, for all we know, those regular mutants could be what happened from certain humans being exposed to the environment with a few other catalysts, perhaps radiation or volatile chemicals, for about three hundred years, and then when the Black Omen came into existence, Queen Zeal plucked a few of them and mutated them even more with experiments using Lavos's magic.
That means you're killing really tripped out people when you fight them.
You
monster.