We have the same issue: when particles are crossing morethan than 100 million, it takes huge time to simulate.
upto to 95 million—each frame takes 4 minutes for sim
Morethan than 100M—each frame taking 42 minutes suddenly

Platform and hardware? That type of behaviour suggests you've hit the GPU ram limit and then it incurs massive overhead to swap between main memory and VRAM. When it suddenly shoots off the roof like that, the first thing to try is to force CPU only as mentioned earlier in this thread [www.sidefx.com].