I recently upgraded to both Parallels 13 and macOS High Sierra 10.13.2. I use Parallels occasionally for vmWare administration and noticed Windows start times went from seconds to minutes.
After much digging around, I finally stumbled on this article at the Parallels website. It turns out, Avira anti-virus (the AV package I use) locks the VM file and causes contention for the VM file. The article outlines a method to exclude the PVM file directory from Avira.
After performing this quick change, launch time for Windows (and Ubuntu) VM's went from 10+ minutes to about 25 seconds, definitely back to where it was before the updates. Definitely worth the look if you're experiencing those issues.