Should I remove existing drywall before framing a wall around HVAC ducts?
It doesn't really matter either way. You'll have to do the same work to finish the drywall in either case.

If it's an exterior (insulated) wall, then cutting the drywall without damaging the vapour barrier is a bit tricky. I usually try to avoid cutting exterior walls for this reason alone.

Benefits to cutting the drywall:


If it's an interior wall, you might be able to put the duct work back into the wall cavity a bit deeper (or even entirely -- I don't know the entire situation). At the least this might help to have the bulkhead protrude out into the room a bit less. 
You can be 100% sure about attaching to existing framing. This isn't hard anyway, but opening makes it a bit easier.
You can add cross-members for support if necessary, such as if the edge of the new bulkhead doesn't line up with the studs.


So unless you have a compelling reason (mostly one of the above), I wouldn't bother cutting existing drywall.