Someone just asked Weekes on Twitter:
" Can you say where in Thedas Solas was while he was in uthenera?"
Weekes: NOPE (all caps like that)
Hmmmmm
Playing DA2 again, and I reckon he might have been not too far from Kirkwall, actually.
Flemeth was transported to Sundermount because a) she needed to get around Morrigan, and
she had 'an appointment to keep', in her own words. Bear in mind that it took Hawke a year to get her then, and even then she was surprised the amulet had made it there at all in such good time, which explains the time discrepancies perhaps (this occurred ten years before the breach). Flemeth had by that point been living in the wilds for years - hence, 'witch of the wild'. I doubt she'd relocate for anyone unless it was incredibly important, and I really can't think of anything more important than preparing for the awakening of the dread wolf. I strongly suspect she has part in it.
I think this case is strengthened further by the obscure codex entry you get in the Black Emporium in Act 3: The Emergent Compendium. Amongst the newest pages in the compendium, there is this: "Two shadowed spheres among stars subtitled "aboofqp iboxE'kbC px bpmfizb kX", where the latter half of that translates to 'an eclipse as Fen'Harel stirred'. This would be around 9:37ish Dragon, which is by Solas' account actually too early, but it's possible the power needed to eventually awake him was gathered from the eclipse. Even if this wasn't the true awakening, some kind of magical ritual occurred within the timeline of DA2 which affected Fen'Harel in some way. Mythal's followers were able to find his sanctuary, so I really doubt it'd be too strange if Mythal was able to find and enter where he was in uthenera, particularly if he does turn out to have previously been her guardian before the fall.
Assuming Flemeth is still in the Free Marches (admittedly she could have just been trying to lose Morrigan and would travel freely from that point on), her location during the events of DA2 is probably also Solas' location. So I'd guess, 'not too far from Kirkwall'. Helps also that the veil is thin there, and there'd be symbolic value in having it close the site where the Magisters first attempted to enter the black city.