eZ publish currently scales to around 500.000 objects. We are running several projects with an object count close to this.
The tree menu of course does not scale to that many objects (the amount of data alone would be far more than most connections can handle). Therefore it is configurable; you can configure what object types to display, the max depth to display and the maximum number of nodes.
Thanks for your comment. Do the hardware needs climb noticeably for the same amount of traffic on large sites or will I mostly be fine with the same hardware for the same amount of traffic (we will try to pack DBs in RAM, of course)?