Tags API isn't paginated when a search filter is used

Summary

The tags API documented here: https://docs.gitlab.com/ee/api/tags.html is paginated. When we make a request to it like: /api/v4/projects/25/repository/tags?order_by=updated&sort=desc the body has just 20 items, and the response headers contain:

< link: <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=2&per_page=20&sort=desc>; rel="next", <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=1&per_page=20&sort=desc>; rel="first", <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=1276&per_page=20&sort=desc>; rel="last"
< x-next-page: 2
< x-page: 1
< x-per-page: 20
< x-prev-page: 
< x-total: 25514
< x-total-pages: 1276

But when we make a request with the search=foo parameter:

It takes a very long time
We get thousands of items in the body of the response.
The pagination headers still act like it was just giving us 20 results.

No amount of changing the per_page or page parameters gives correctly paginated results.

Steps to reproduce

Make an API request for a repository's tags using the search parameter

What is the current bug behavior?

The results are not limited by the per_page parameter and the pagination headers returned are not correct and the query takes a very long time.

What is the expected correct behavior?

The results are limited by the per_page parameter, the pagination headers are correct, and the query is relatively quick.

Relevant logs and/or screenshots

# Request the tags API without search, get good paginated results:
$ curl --verbose 'https://gitlab.example.com/api/v4/projects/25/repository/tags?per_page=200&order_by=updated&sort=desc' > tags.json
...snip...
< link: <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=2&per_page=200&sort=desc>; rel="next", <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=1&per_page=200&sort=desc>; rel="first", <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=128&per_page=200&sort=desc>; rel="last"
< x-next-page: 2
< x-page: 1
< x-per-page: 200
< x-prev-page: 
< x-runtime: 0.312596
< x-total: 25536
< x-total-pages: 128

# Check number of items returned
$ jq 'length' < tags.json 
200

# Request the tags API with `search`, get bad paginated results:
$ curl --verbose 'https://gitlab.example.com/api/v4/projects/25/repository/tags?search=^build&per_page=200&order_by=updated&sort=desc' > tags.json
...snip...
< link: <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=2&per_page=200&search=%5Ebuild&sort=desc>; rel="next", <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=1&per_page=200&search=%5Ebuild&sort=desc>; rel="first", <https://gitlab.example.com/api/v4/projects/25/repository/tags?id=25&order_by=updated&page=128&per_page=200&search=%5Ebuild&sort=desc>; rel="last"
< x-next-page: 2
< x-page: 1
< x-per-page: 200
< x-prev-page: 
< x-runtime: 51.728983
< x-total: 25536
< x-total-pages: 128

# Check number of items returned
$ jq 'length' < tags.json 
19168