I have worked with sorted sets with millions of items. The latency really depends on what you execute. Commands that involve only few elements are fine. Like the ZPOPMAX you mentioned should be way under a ms if you pop say 10 items, and you should be able to get way more than 1k QPS. The thing with sorted sets like most data structures in Redis is to just read the time complexity well in their documentation. For an operation like ZPOPMAX it is linearly proportional to the number of items you pop, so if you pop too many it will take time.
>>actuat+(OP)
But actually ZPOPMAX is proportional to log(number of elements in set). So when the set grows to millions you may have a performance problem. I have no idea how fast growing this log function is so I really have no idea of the performance on sets of millions...
>>etaioi+J61
Well, that represents the asymptotic time complexity. So, roughly with an increasing N it increases by log of it. Here is an example of the log(base 2) function growth.
Assuming other things remaining unaffected, theoretically that means in a set of 4 million the operation should be about 4 times slower than in a set of 250 elements.