I think for fun you should create a dummy page that just create 40 million rows, repeated without going to the database, and then show this to your customer. If they can load it without their browser crashing and be able to look through it easily, then continue.
This is more of a case of a customer not understanding what they are asking for than a technical issue.
BTW here's an article on
Pagination that may be useful. Do your really think when Google says "About 10,200,000 results for your query" they have a system designed, or ever expect, users to iterate through 10+ million results? What it sounds like you need, besides pagination, is a search engine built on top of your data. Granted, in this instance, simple database indexes may suffice.