Alexius can roll time back up until the Breach was created. The mages say Alexius came to Redcliffe about 2 days after the conclave, but you could assume he rolled time a bit further back before he arrived.
Fiona tells us that Alexius had already planted Tevinter sympathizers among the rebel mages before he made his grand entrance. After all, the rebels were taking mages from all places, Ostwick, Ferelden, Montsimmard and Kirkwall, they can't really kick some one out because they look foreign.
These Tevinter sympathizers might have appeared frazzled, out of breath, terrified, bringing the news that the Most Holy has been killed and they are pinning the blame on the mages. Without the Divine to speak for the mages, the templars have gone mad and are gathering a legion to march on Redcliffe to kill the mages. The Tevinter sympathizers might slip that the more devout of the Ferelden noble men as supporting their templars and pushing for the King/Queen to kick the mages out.
At the same time, representatives from Arl Wulff (and probably some other nobles) arrive, giving similar tales. The templars thirst for blood, many nobles with connection to the Chantry are sending the mages the evil eye and it seems that Ferelden is no longer a good place for a mage to be.
They talk to Teagan, reminding him of how fearful many people are of mages and how this tense the situation is.
Most of the rebel mages grew up in the Circle, under the watchful eyes of the Templars. All the circles probably had an Alrik, Meredith or Karras type, who declared loudly that they hated mages and longed to wet their blades with mage blood. Now, the infiltraters move amongst the mages, making it sound like these types are leading the templars. Remember the destruction at Kirkwall? It's heading to Redcliffe.
Panic spreads among the rebels as they brace themselves for the slaughter. But behold! A magister from Tevinter arrives with his men. He looks at the mages with sympathy, expressing concern for his "Southern Brethren" and "fellow mages". He claims to be here at the behalf of the Imperium, who do not wish magical blood wasted on the Templars. He preaches safety, comeradery and the opportunity to finally have the right to build their own lives. He points at the children, should they be slain in this war? Should their lives be wasted when they could be embraced into the Imperum? A land which values their talents and encourages them to grow instead of demonizing them and locking them up?
So he gets to come in, to offer some moral support for the mages and try to figure out a solution with Teagan and Fiona. The Imperium would love to get the mages, but there are some legal issues, you know? And the mages need to be integrated into the society and prove that they will benefit the Imperium. The process can take up to ten years, in which they'll be indentured to Alexius and he'd have them do work that proves their value. He sells it like they'll be doing research, studying and sharing knowledge with Tevinter. Maybe the hardier mages would help the army, getting to finally use their magic as they should.
While he butters the idea to Fiona, his soldiers start to mingle with Teagans men. They have a bit of a chat and decide that having so many Chantry priests and tranquil hanging around is making the mages more tense. That it might be better if Teagan went some where else while the situation calmed down. And eventually, Teagan finds that he and some loyal Soldiers are being "escorted out" to "keep the peace" along with most of the Chantry priest. And nobody is objecting.
Now Fiona finds herself alone negotiating with Alexius. Alexius brings the mages who approve signing on with Tevinter to the castle and maybe one or two of those opposed (but picks those with less convincing arguments :Tevinter is evil because it's ruled by mages! The templars say they are all demons) , to the Castle to talk about the idea.
He also brings the children into the Castle, because they can't have them sleeping in the stables can they? No, they should be amongst their friendly Tevinter brethren. Now Fiona is surrounded by people pushing for the opportunity to move to Tevinter, making it look like it's what the majority wants.
As far as she know, the rest of the world hates the mages and already sees them as no better than the Tevinters. Everyone wants them dead, except for Tevinter. The inquisition is at the moment just a tiny order, not some Heralding saviors. 10 years is a long time, but death is even longer.