I can add a bit more info (based on some knowledge of the internals).
In R80.x, the new cpm process & Postgres have indeed given us new capabilities and the ability to handle many operations using multiple threads. Much of this cannot be applied to logic that still runs under fwm.
Fortunately, the smart people who worked on policy installation in R80.10, created a mechanism that will perform the policy verification only on the delta of changes. The way that this is done, is that cpm "dumps" the full policy for fwm, but also outputs the IDs of rules that have actually changed since the last policy installation. Then, the policy verification code takes that into account to optimize the policy verification (mainly the rule-hide-rule calculation).
Due to this mechanism, the first policy verification (after import or upgrade) may take some time, but the next one should be much faster.
In addition, we are working on another improvement for R80.40 that will make the verification significantly faster (especially with large rulebases), even on the first run.
Question: Did you happen to notice if there is a difference between your first time and the subsequent attempts?
Also, 10 minutes is quite a long time for a policy of 1500 rules. If this didn't improve, I would suggest opening a TAC request and they can help you check the environment to see if there is a reason for this (possibly other load or HW).