Recently I moved one of my email adresses from a hosting package on uberspace to google mail. Normaly there is a migration tool which does the migration for you.
Unfortunately it requires a login without encryption or SSL. Uberspace only supports encrypted logins (which is a very good idea) but just STARTTLS and TLS but not SSL. Google also offers two other tools for migration, but they are only available on Windows.
It's possible to add both accounts (old and new one) to your mail client and move the messages by drag'n drop. But that is both unsave (especially with a high volume) and very slow as it has to upload and download all messages on the client side.
A better way is to use imapsync. It's a command line tool installed on uberspace (and a lot of linux distrubutions) which does exactly what the name suggests: Syncing imap accounts.
You define the hosts and the users (email adresses) with passwords (in files). You can also set them directly with other options )
imapsync \ --host1 localhost --user1 email@example.com --passfile1 password-local.txt --authmech1 PLAIN \ --host2 imap.gmail.com --user2 firstname.lastname@example.org --passfile2 password-gmail.txt --authmech2 LOGIN --port2 993 --ssl2
I had to start the process multiple times, because it stops as soon as an error occured. The error in question was the size limit of attachments. With Google Mail it is set to 25MB.  (I had to manually delete the big attachments)
Still, it works like a charm. As it runs on the server side, it's reasonably fast and it continues where it left of when you quit it. I got all my messages transfered and it even works if you use alias domains in gmail and merge multiple email accounts into one google mail account.