Figures from Bernard Bernier, "Capitalism, society and culture in Japan". Mr. Bernier was at the time of publishing a member and teacher of both the department of antrophology and the East Asian studies center of the Montreal university.
VIIIth century - Nara at 100 000
Xth century - Kyoto at 500 000. I believe I've seen somewhere that it had reached the million mark by the time the Europeans dropped by.
Edo, which as you notice got started quite late, more than made up for the late start, hitting the 500 000 mark in two centuries (1650) and the 1 000 000 in less than three (1720), catching up to London around 1650 and outstripping her shortly after that to eventually become the more or less 20-millions megalopolis we know today.
Osaka hoovered around the 300-350K marks circa the same era (quoted in the book I mentioned as being a third of Edo's in the early 1700s).
Amenhotep - the problem with that little snippet is easy to see : Tenochtitlan by the time it was built only rivaled with the late-medieval, early-renaissance Rome, which had nowhere near its Classical population.