What affects the speed of a count(*) besides the number of records
Bear in mind that the query plan shows an estimate of cost which is not the same as time.  The estimated cost values are a unitless aggregation of CPU, memory, and IO, not how long each operation takes to execute.  Also bear in mind that the cost values are estimates even in an "actual" execution plan.

The biggest bottleneck for this and most other SQL Server operations is disk IO.  Your example STATISTICS looks to be from a second run since there are no physical reads, though, so you see a higher CPU which is used for the aggregation/sorting.

You may be able to speed this particular query up with a filtered index, if your WHERE predicate is consistent (i.e. always Bar = 1 AND Baz = 2).

Otherwise I'm not aware of a way to speed it up beyond something more drastic like an indexed view.