API pagination headers cause queries to slow or time out

The API has a helper paginate that attempts to count the total number of items in the request: https://gitlab.com/gitlab-org/gitlab-ce/blob/792e9ed7fa46d236c01fb14c8ad7f9b4ea4dee59/lib/api/helpers/pagination.rb#L15

This leads to queries that take a long time (over 10 s), such as:

SELECT COUNT(*) FROM "ci_builds" WHERE "ci_builds"."type" IN ('Ci::Build') AND "ci_builds"."project_id" = 13083

https://gitlab.com/gitlab-org/gitlab-ce/issues/42026 is also related.

What can we do about it? Some ideas:

1. When the counts exceed 1000, don't include the exact number of pages because counting takes too long.
2. Cache the counts, increment/decrement in Redis

Caching doesn't seem like it will work well because API requests can have different parameters that affect the actual query.

This is quite similar to https://gitlab.com/gitlab-org/gitlab-ce/merge_requests/16392/diffs, only this affects every one of our API requests.

/cc: @yorickpeterse, @_stark, @matteeyah