That would be the first step; the rest involves setting up some kind of IPC between "parent" and "child" so that the icon menu can influence the main script's processing.
An anonymous monk provided a better solution: simply call Win32::GUI::DoEvents periodically in your code. Note that this option means that the icon will be unresponsive until a DoEvents call is reached, so it does need to be called fairly often, such as on each iteration of any time-consuming loop.
I use Tk on X11, so I am not particularly familiar with Windows GUI programming, but this seems to be similar to the type of problem I have solved in the past by forking workers and having them return results back to a main GUI process using pipes. In your case, the issue is a bit more complicated by the need for the GUI to be the side task. The *nix traditional solution would be to write an event-driven GUI wrapper for the command-line program but I do not know how well this strategy will work on Windows.