You had me concerned for a second, but "mists of time" shows up on Wiktionary (easier to be wrong), Merriam Webster's site (likely to be right) or the Oxford English Dictionary (practically canonical), whereas "midst(s) of time" does not.

Collins Dictionary and Dictionary.com don't list either, but the existence of the former in other places would seem to suggest that that's the right one.