First of all I would say don't believe everything you read on the Internet! Second of all, if this ever was true in older versions of Prestashop I can confirm it definately is not an issue in Prestashop v1.6. The optimisation and caching built-in are excellent, and with a well written theme and templating it is possible to have a very fast/responsive store.
I recently had the requirement of a large product catalogue for one of my customers (approx 800,000 products) and already using Prestashop for many other customers, and after reading dh42: Prestashop Scalability on AWS I was tempted to give it a try.
I can confirm that by utilising either a content delivery network (CDN) or such as an AWS S3 bucket for images, and a reasonable AWS RDS instance for the MySQL database (e.g.
db.r3.large) Prestashop can manage a very large product catalogue without any difficulty and with easy future increased scalability, the only tricky party is getting the AWS instances and configuration setup if you're not familiar with it - this was a steep learning curve for me. I didn't go to the same lengths as were described in the article I referenced but I didn't need to cater for 5000 conconcurrent users either. By the time we worked out the cost of running all the necessary instances on AWS it actually worked out cheaper for us too than the previous VPS hosting arrangement. The site I'm referring to was moved from VPS and published 'live' on AWS in January 2015 and after nearly 5 months I have only been impressed with the final outcome, though it took some serious tweaking in the first month, and we even downgraded our instances from those we originally chose and were still very happy with the performance.
I believe there can still be more work done to improve the scalability of Prestashop, however it is certainly possible at present to get a very fast responding site with a large product catalogue if setup correctly and on hosting infrastructure suitable for the requirements.