If so, then why Flemeth speak of a betrayal?
Catch a spy isn't a betrayal.
As Caddius suggested, Mythal and Solas may have felt betrayed by how corrupted the Evanuris had become. Solas states that the Evanuris rose to power as generals during a terrible war, implying that they may have once fought to save the Elven people from destruction... only to later threaten to cause the destruction of everything themselves with their lust for more power.
The personal betrayal would be when her husband and her former friends decided to brutally murder her for opposing them. How or what they did to her we don't know, but it was enough to leave her a bare wisp of what she once was, taking centuries to gather enough strength to recover as suggested by Flemeth.
However, perhaps he rose to his position from a simple background. Remember how he mostly lied by omission (mostly). He says he grew up in a small village. Maybe he was born a commoner indeed, then became evanuris later.
Solas would seem to suggest this in Trespasser, as he does tell us the Evanuris were soldiers who became generals, then ended up as God-Kings. Him having a common background, joining the military and then ended up in a position of power would all fit.
Of course, that depends on whether he was telling the truth, but I am inclined to believe he was. While he says he doesn't want to tell us everything about his future plans, he does pretty much lay all his cards down on the table for us at the end of Trespasser, when he really didn't need to.
Personally, and this is just me mind you, I think it is unlikely that Mythal was a spy for Solas. I just can't see her conceding to that kind of role. From what I've gotten from her character she is too used to be the one controlling the spies to be one for someone else. That said I could see it as possible that she sent Solas to start freeing the elves, but that also doesn't quite seem right given Solas' adamant passion against all things slavery/anti-freedom it seems more like a rebellion/passion he would have started on his own.
Well, I meant to suggest earlier that the two were probably working in tandem.
I do agree that Mythal would be more likely to be the ringleader using Solas as her agent of change, based on both their characterisation and the nature of their relationship that's implied. So Mythal would have been less a spy working for him, as more of an M to his Bond, keeping her agent apprised of vital information that he needed to know to help carry out their plans.