I don't necessarily believe that the Gerudo started out with a male predecessor. When I think about the Gerudo tribe, I think of Wonder Woman first. Wonder Woman for those that don't know, originated from an Amazonian tribe that only consists of females, much like how the Gerudo are all female except for the one man who is to be born every 100 years. The only difference between the two tribes is that the Amazonian tribe never mentions anything of men contributing to the tribe in any fashion, at least that's how much I remember of the comics as I haven't caught up to Wonder Woman in a long time. But because of their absence of having no man ever be a part of their tribe, it makes me believe that the tribe did in fact start as a female tribe and I think the same could be said the same with the Gerudo.
What could possibly further prove this theory are the surrogate mothers of Ganondorf, Koume and Kotake. If you take a look at their appearance, you will notice that they look older than the average Gerudo woman. I do want to point out that after checking and observing every Gerudo in Ocarina of Time, they are probably the oldest in terms of appearance and could potentially be the two women who started the Gerudo tribe in the first place. It is quite possible that they are when you consider they are the only two Gerudo women who know how to use spells or magic and their base power of magic appears very powerful which could mean that they have been practicing their spells for who knows how long, maybe even as long as the generations the Gerudo tribe has existed for.
Those are my two cents on the latter and whole I believe there might be some flaws or hopes in this theory, I do believe that there are points in my theory that could be potentially true.