I've had the this same issue for at least a couple years now. I created this extension to "fix" the issue. It looks for related records (phone,email,address) of a contact and when none, or more than one are set to primary it sets just one to primary. Uses the sites default location type for primary.
That's almost certainly a timeout issue - you can increase your timeout in php.ini, but I wouldn't use the UI at all for a million contacts. Consider using a command-line import, where there should be no timeouts.
There are several approaches you can take.
Use the command-line API CSV import. This is pretty solid but you need to import each file multiple ...
It depends on the job.
Import jobs (Contacts, Contributions...) work by having one long-running POST request, and then your browser polls for updates on progress.
This means your browser/server/interenet connection need to be able to cope with the time that POST request requires. Whether a job completes after apparently timing out depends on how PHP is set ...