If your performance degrades significantly as you add rows and you have good indexing, one of the most likely culprits is a poorly written query. This is why we can't say for sure at what point it would happen, it depends greatly on exactly how you are querying your database and your database structure.
Some of the common things that can work fine in small data sets but which often work badly in larger sets:
cursors
correlated subqueries
wildcards in the first character of a where condidtion
functions
non-sargeable where clauses
forgetting to index the foreign key fields