Extreme slowness with thousands of pages

I have a client that needs/wants 16,000 pages hierarchically organized (Continent -> Country -> Region -> Ethnic People Group. With lots of ethnic people groups being repeated in different regions).

After creating these pages WP slows to a crawl any time any one of the pages are edited or displayed. Apparently the entire hierarchical structure is traversed each time any page is accessed.

I’ve heard of huge WP installations with thousands and thousands of posts so I’m surprised that I’m having this issue. I’m thinking my best option would be to convert these pages to posts and create a hierarchical menu using jQuery. Is that my only course of action? Would there be any advantage to using custom post types?

Thanks!