You wouldn't have to re-create it. You could just create an update set and add that flow specifically to it. It will then capture the flow and you can move it between instances.
The flow has a number of different records on different tables that makes moving it outside of an update set or app scope difficult. If you've created it outside of an update set you do have a couple of options for getting it into an update set:
Open a new update set and use the copy flow functionality to create an identical flow that will get captured by the udpate set.
Use the Add to Update Set share utility to add the flow to an update set. (I'm pretty sure it has the capability, but I haven't used it in a while and it's not in the notes on the share site)
