Have you looked at Mail::Bulkmail? I've used it to send 485,000 mails out and it handles it without a problem.

I doubt Mail::Mailer is the problem (I've never used it), it might be your sendmail configuration that is at fault. We use postfix so that we can limit output threads.