It's going to vary quite a bit based on your specific org and the data model in your org.
It may be helpful (at minimum, interesting!) to read Best Practices for Deployments with Large Data Volumes. The section on Reporting offers a few suggestions, but it's not in a great deal of depth. Understanding the concepts introduced in that document can help to highlight which specific kinds of data volume + data model + query or report structure combinations end up being problematic for performance reasons, and which conversely will let a big report get through inside the time limit.
Just to give a couple of bounds that illustrate how much variance there can be, I've caused report/query timeouts in an org with as few as 200,000 records on the primary query object (and I'm sure it's possible below that!)
I've also worked in orgs with more than 10 million records in an object, where virtually no query or report on that object will complete successfully without close attention to how the joins are designed and to the use of custom indexes and skinny tables, which had been architected specifically to facilitate report building.