I'm wondering if we're talking about different things. If it takes 1 second of CPU time to process the path for 1 package, then it will take 1 million seconds

I'm wondering if we're talking about different things. If it takes 1 second of CPU time to process the path for 1 package, then it will take 1 million seconds of CPU time to path find 1 million packages. You can add more CPUs to run multiple path finds in parallel (ie, use 4 CPUs to cut the wall time to 250,000 seconds), but there's still 1 million core-seconds being spent.