Practically, over 1Millions leads, you need to start paying attention to performance optimization (and even above 700k, from my experience, if you are running a lot of smart campaigns).
Adobe is pushing Adobe Campaigns rather than Marketo for customers who need to have 10 millions + leads in their database.
Keep in mind that the licence cost is directly linked to the number of leads in the database, though.