The size of the table isn’t really the issue, the queries you’re running on that table might be.
For example, if you’re selecting users based on data stored in the user-meta table, then that query will be highly unoptimized, because meta_value is not an indexed field. In which case you may need to add extra indexes or consider storing that particular data in a different manner, such as with a custom taxonomy.
Generally speaking, stuff that you store as meta should never be something that you will exclusively search based on. This applies across all the meta tables in WordPress. Meta is mainly designed to be pulled out by the meta_key, not by the meta_value. Taxonomies limit the possible values to a set and organize the information differently, so they do better when the “value” counts as what you’re selecting on.
Note, selecting by both meta_key and meta_value is generally okay, because mySQL will optimize the query to be based on the meta_key first, reducing the amount of data to search to a (hopefully) manageable limit. If even this becomes a problem, you can “fix” it by adding a new index to the meta table with both meta_key and meta_value on the index, however because meta_value is LONGTEXT, you need to limit the length of that index to something reasonable, like 20-30 or something, depending on your data. Note that this index may be much, much larger than your actual data and will drastically increase the storage space needed. However, it will be much faster at those types of queries. Consult a qualified DBA if this ever becomes a real issue.
For reference, on WordPress.org we have approximately 11 million users registered. The amount of meta varies per user, with probably a minimum of 8 rows per, and maybe a max of around 250-ish. The users table is about 2.5 GB, the usermeta table around 4 GB. Seems to run okay, for the most part, but every once in a while we find some oddball query that we have to go optimize.