The meaning of "female master" came first. The second meaning of "illicit lover" seems to follow quite naturally to me. I don't have any documentary historical evidence to back this up, just my intuition, but it seems quite natural that people would think of an illicit lover as dominating (domina + ing) her boyfriend through her seductive powers. He is enslaved to her through his lust and her charms. The usage is not literal but whimsical.
I doubt that it has anything to do with dominant women in the sense of women with forceful personalities, and even less likely that it has to do with women of high social or political status. Maybe I'm applying modern connotations to antiquated usage here, but if a man was having an affair with the queen, I don't think he would call her his "mistress": that would be demeaning to her, and I presume he wouldn't dare.
It is common for men to talk about their wives half-joking as being dominating, even if she is not a very domineering person. When he changes his plans to appease her or consults her before making some minor decision, he often comments on how he "must check with the boss" or follow "she who must be obeyed".
This isn't a new idea. I can't find the quote right now, but I recall reading a quote from an ancient Greek king to his wife that was something to the effect of, "All Greece is ruled by a 2 year-old child. For our son rules you, you rule me, and I rule the Greeks."