Recently, I decided to add an index of subpages (300k), 250 items on each, with pagination. - Could this be more effective than 'sitemap' and can they co-exist together, or it will be bad for the crawling budget?
You are describing an HTML sitemap. Before XML sitemaps, it was very common to have HTML pages on your site whose only purpose was to link to all the sub-pages. XML sitemaps have largely supplanted HTML sitemaps.
HTML sitemaps are low quality pages with thin content. They are not very useful to visitors. Search engines don't want to index them. They are more likely to hurt your SEO than help it. I would recommend removing HTML sitemaps from your site.
Neither XML nor HTML sitemaps will help you get hundreds of thousands of URLs indexed. To get massive amounts of URLs indexed, your pages should cross-link to each other so that they pass your site's reputation around between them. You will also need to work on building your sites reputation by getting high quality external links from other relevant sites. The whole process takes time, often a couple years.