You asked about (1) the reason for a slow boot time when shutting down via Start menu -> Shut down.
That is expected behaviour when you have Fast Startup enabled, and it was covered by harrymc.
You can easily confirm that this is the reason for a slow boot by disabling Fast Startup and checking. You can also try Restart instead of Shutdown+Startup (see also this, among the many sources available), that should produce a faster startup.
A further reason for a slow boot is when updates are applied, but I assume you are not referring to that case.
I understand you are especially concerned about (2) why this would only start happening after setting up a dual boot with Linux Mint. That is actually strange, since what you found is also expected without dual boot.
The only explanation I find is:
- Somehow you enabled Fast Startup at about the same time you set up dual boot.
- You started having more applications that restart upon boot at about the same time you set up dual boot.
You could make a few tests (e.g., with/without Fast Startup, using Shutdown/Reboot).
This will of course not answer question 2, but it helps with question 1.
Note that it is often recommended disabling Fast Startup when dual booting, as it may have issues when mounting the Windows partition in Linux, e.g.
This information is complementary to the answer by harrymc, as it refers to the same possible cause of slow restarting.
This shows various forms for shutting down, including hybrid shutdown (fast startup) or full shutdown.
This shows how to add a context menu that helps selecting the method for shutting down.