We have a job with 141935 builds (at time of writing).
Clicking the latest succeeded or failed builds from the main view works fine, and is fast. The "previous build" links are fast too. But I can't load the job summary page (i.e. $JENKINS_URL/job/jobname), or manage it, or anything on a per-job rather than per-build basis.
Anecdotally, the problem seems to have started since we upgraded to 1.638 (for the security vulnerability) from 1.632