Why is a paginated query slower than a plain one with Spring Data?

It might indeed be the count query that's expensive here. If you insist on knowing about the total number of elements matching in the collection there's unfortunately no way around that additional query. However there are two possibilities to avoid more of the overhead if you're able to sacrifice on information returned:

1. Using Slice as return type — Slice doesn't expose a method to find out about the total number of elements but it allows you to find out about whether a next slice is available. We avoid the count query here by reading one more element than requested and using its (non-)presence as indicator of the availability of a next slice.
2. Using List as return type — That will simply apply the pagination parameters to the query and return the window of elements selected. However it leaves you with no information about whether subsequent data is available.

Method with pagination runs two query:

1) select count(e.id) from Entity e //to get number of total records
2) select e from Entity e limit 10 [offset 10] //'offset 10' is used for next pages

The first query runs slow on 7k records, IMHO.

Upcoming release Ingalis of Spring Data will use improved algorithm for paginated queries (more info).

Any suggestions?

I think using a paginated query with 7k records it's useless. You should limit it.