One approach would be to use Perdition for POP/IMAP connection handling and then just setup your Postfix to route SMTP to an old or new server, depending on where the user mailbox is located. This way you can migrate your server live one mailbox at a time without any downtime.
Of course you can setup a scheduled maintenance break, and then just rsync the files. Copying 15 million files WILL take a while, though. Depending on your server and mostly, the I/O system, it might help to run several rsync processes in parallel; one copying files/dirs starting with [a-e], second one with [f-j], third one with [k-p] and so on.
But having done a similar thing twice, I would recommend the Perdition approach. After initial setup it truly takes the migration pain away.
EDIT: You asked for more info about Perdition setup, you got it.
You need to have some central place where you have your user account information stored. That can be MySQL, PostgreSQL, OpenLDAP or something else. I have always used OpenLDAP with great success. Anyway, you need to have a database table / LDAP schema which contains the user name and the server name where user mailbox is located. There are Perdition migration utils available which will help you in the initial setup.
Then Perdition receives the POP/IMAP connections, looks up user location from LDAP or whatever, and transparently proxies the traffic between the user mail client and the actual server. Postfix can also lookup this actual server location from LDAP/SQL and send the mail there.
Here is a PDF about Perdition + LDAP setup and here is the Postfix LDAP manual.
Next just create a migration script which copies the mailboxes one by one over IMAP with imapsync
or similar util, and after each successful mailbox migration it just should update OpenLDAP or whatever central location about the user mailbox location.
EDIT #2: The imapsync I'm talking about is free software, and available in most Linux distributions from their package repositories. You asked me to elaborate more about rsync
approach; it does not matter if you choose imapsync or rsync, the basic principles are the same. You just create a script with bash, Perl, or some other language you feel comfortable with. Here's some pseudo code.
@accounts = fetch_all_the_account_names_from_ldap();
for (@accounts) {
rsync -avP /var/spool/mail/$user $newserver:/var/spool/mail/
update_user_location_in_ldap($user, $newserver);
}