Putting URLs in a sitemap does not usually mean that they will get indexed. Googlebot will usually crawl all the pages in a sitemap, but the decision of whether or not to index pages is based on how unique and popular they are. That popularity and authority is measured via inbound links to the pages. If you have pages only listed in your sitemap and never have links to them on your site that Googlebot finds, they almost never get indexed. Even if they do get indexed, they won't rank well for anything competitive. All in all, sitemaps are nearly useless for SEO. See The Sitemap Paradox.
Pagination is also nearly useless for SEO. Googlebot will follow the links in pagination and usually crawl a ton of it. However, by the third page of pagination, there is usually no authority (PageRank) left from the first page. Google will probably not chose to index pages found beyond the first page of pagination. Having crawlable pagination is not good for SEO. It also turns out it is not great for users. Fewer than 5% of users ever use pagination, and of those that do, only a fraction ever make it past the second page.
So what should you do?
If neither pagination, nor sitemaps are great for SEO, what should you do?
- List as many products on the first page as possible. Having a list of 100 products on the first page is not unreasonable.
- Link each product page to other related product pages. Each product page should have links to related products. Such links are usually in sections like "Similar products", "compare with", "people that viewed this ended up buying", or any number of other variations.
- Provide search functionality for users. While it won't help with SEO (and you should block search bots from crawling site search results), users like to find products via search.
- Implement faceted navigation. Users like to be able to drill down and select products by attributes. Search engines should be allowed to crawl pages with exactly one facet applied. For example "X Brand widgets", "Widgets under $100", or "Widgets with feature X".
If you end up providing pagination to support the small number of users that do use it, that is fine. I usually recommend not making it crawlable anyway because it doesn't help with SEO. Your plan of using pagination without crawlable URLs won't hurt your SEO, but there is no way that it will help it.
As far as rel=prev and rel=next go, it would only make sense to use them on a series of crawlable pages. When you don't have crawlable pages, it wouldn't make any sense to use them. In any case, it shouldn't matter for SEO because Google recently admitted that it hasn't used rel=prev and rel=next for years anyway.
