NothingNow
Banned
Something like that, I just jumped to a quick refence website for Tokyo because it is well known. I don't even think it's close to the top of the list of megacities these days, but archology city-in-a-buildings frees up a lot more space.
Well yeah, but they're a pain in the ass to engineer if you build too tall, and it's not always obvious things too (Taipei 101's settling has caused small, but detectible earthquakes in Taipei, since it was built atop a closed fault line.)
We can achieve 40,000 people/km2 pretty easily just by building at the density of Hong Kong Island and Kowloon (which together are at ~35,700/km², while Kowloon exceeds 43,033/km2.) Meanwhile, the densest ward in Tokyo, Toshima, only has a population density of about 20,600/km2, (but only about 47% of the ward is residential, and the residential buildings in Tokyo aren't Skyscrapers usually while 40 stories seems kinda normal for Kowloon, so the comparison is kinda bad, but it does point the way forward.)
Estimating that about 35-40m2 per person would be suitable in terms of residential units (the approximate standard in much of the world, but somewhat tight for americans,) you could get away with building units between 70 and 160m2 (753-1722ft2,) (2 bed/1 bath at 70m2 to 3-4/1-2 at 160m2.) so that might be a good jumping off point for serious calculations.
But something like 40-50 storys could be fairly easily achieved architecturally and systematically, and would provide a higher density than Paris, with more open spaces and more comercial space. Most of the New Towns in Singapore manage Parisian densities with much lower buildings than that. Ang Mo Kio for instance has a population density of 23,777/km2 overall, and about 53,600/km2 counting just the residential areas, achieved with just 12 and 25 story blocks.