Hi,
Yeah, for 40K products, a site map with the products added to it is not a solution.
First turn on the "Show shortcuts to other category products" setting of the HikaShop configuration. That will add previous/next links to each product page allow your users and also google to easily access all the products even if it has a hard time to follow the pagination.
I've checked a bit your products on google, but even the ones not on the first pages are searchable in google.
So Google already knows about them, meaning that google was already able to follow the pagination.