Indexes and compound indexes tend to become slow themselves when you end up indexing a significant fraction of the columns or when your result sets are a significant portion of the total for count. They cost extra time and space to update on write. If your database has concurrent writes going on Postgres still needs to verify which row versions are visible to the transaction on read. The additional pressure on memory and disk means you have a bigger working set. The query planner has a combinatorial number of indexes to choose from
So the planning stage slows down. You have to spend even more time on analyze to keep the estimates (which power this technique) correct etc. At 10s of millions of rows with more than a few low cardinality columns in the filter it’s sometimes faster to just get as much of the table as you can into ram and accept the scan.