You're not easily going to be able to send that kind of volume with Salesforce alone. Sure, you can batch them up as you suggested, but then you will have potential scalability problems. What if you suddenly want to do two mailshots per month? What about any other emails you are sending - if you've used your SF allowance on these big batches, you might not have capacity for those.
If they are marketing emails, and you want to get into marketing automation, then consider using Marketing Cloud, or Pardot.
If you just want to send lots of email simply and relatively cheaply, you will need to make callouts to a specialist email delivery service. I've used both SendGrid and Amazon SES for these purposes. I slightly prefer SendGrid, but it's a bit of a matter of taste which is more appropriate.