I was playing around with CDS' OData API and I noticed that the count of records returned when specifying the $count=true param or when appending $count to the request path maxed out at 5000 regardless of the actual record count. Probably not coincidentally, this also looks like it's the max page size for a response. Quoting the OData v4.0 spec section 11.2.5.5:
The $count system query option ignores any $top, $skip, or $expand query options, and returns the total count of results across all pages including only those results matching any specified $filter and $search. Clients should be aware that the count returned inline may not exactly equal the actual number of items returned, due to latency between calculating the count and enumerating the last value or due to inexact calculations on the service.
The spec allows room for a count to be inexact due to latency or inexact calculations, so maybe this is a grey area. But it feels like taking some pretty extreme liberties to say the actual count is 2000% of the estimate because the count is just inexact. This isn't a huge deal since the pages each provide a next-link if there's overflow, but $count should return a correct(ish) amount or be disabled like $search or $skip.