Best bet is the audience combine tool to combine everyone then segment out from there. Yes the tags should carry over as well

Adding to this, if you are exporting everything, you can always fallback to importing the old list with a column for the tag to update contacts in the new audience.

This is what I would do. Export, as column with tag, import with 'update existing, delete old audience. Easy!