How many taxonomy terms are too many?
Short answers:


Drupal should have no problem with 5000 terms.
Using a taxonomy for this is the best solution in Drupal. 


You may also want to use Taxonomy manager as suggested by kala4e4k in a comment.

What is the upper limit?

Well, taxonomy vocabularies are managed by the database, so this limit is determined by the maximum number of rows you can store in a table in the database you're using.

If you're using MySQL, there is no built-in limit to the number of rows per table (just pick a big enough number type to manage the primary key), but there are other constraints on table size besides number of rows. If you have a 500 Gbyte hard drive and each record is 1 KB is size, your maximum number of rows will be 500 million (if you dedicate the entire drive to this single table, which is not a very realistic scenario). If you buy a 10 Tbyte hard drive, you may run into your operating systems file size limitation (for instance, I believe Ubuntu's maximum is 5 TB, so your limit will be 5 000 million terms instead of 10 000 milion - given the same assumptions about record size).