The patch overrides the row key bounds, so for instance won't work correctly for SELECT count FROM <cf> WHERE key='foo'. It also don't take a potentially provided user LIMIT into account (I reckon it's dumb to give a LIMIT when counting rows but we still need to support it correctly). Also, it only page internal rows, but not within internal rows (and also, makeSlicePredicate creates a predicate with a count of -1, so that won't work with a getRangeSlice call that count keys instead of columns).
I think that unfortunately, to correctly page count(), you need to be able to correctly page CQL3 queries in general, and that is a little bit more work (since we basically need to handle both query by slices, query by names and range queries underneath). I've (just) started work on handling such paging for
CASSANDRA-2478, and I really think there is no point in doing something specific for count.
Getting back to the description of the issue, I note that imo we should stop using a default limit of 10,000 for CQL queries as this is totally random.