What kind of capacity are you using? With the IBM MQ Native protocol it has a max poll period of five seconds, regardless of any other timeouts. This means it should take an average of 2.5 seconds to shut down each thread in your service. The only way I can explain it hitting the 60 second timeout is if your capacity is greater than 24, which is approaching counter-productive unless you have 12 or more cores on your VSE machine.
Try modifying your VSM. Go into the 'Listen' step and enable the 'PRO' button at the upper right corner. Find the 'Scope' field towards the bottom of the step and change its value to 'Staged'. This will force all threads in your VS to share a single connection and polling process, making shut down much faster.