I recollect that:
select count() from Contact
will now work for more than 50,000 rows (but can't find documentation on that improvement).
My question is whether or not there is a new (much higher) limit that applies?
The COUNT query is a special case of aggregate querying, as covered in the documentation:
Queries that include aggregate functions are still subject to the limit on total number of query rows. All aggregate functions other than COUNT() or COUNT(fieldname) include each row used by the aggregation as a query row for the purposes of limit tracking. For COUNT() or COUNT(fieldname) queries, limits are counted as one query row, unless the query contains a GROUP BY clause, in which case one query row per grouping is consumed.
(My emphasis)
In that case if you only do a COUNT then it should in principle be able to count any number of rows since it is considered a single query row when it comes to contributing to limits. However, as mentioned by @David Reed, it may be that applying the query to a very large dataset will simply time out.