OOTB should terminate the process when the object is deleted, shouldn't it?
Find the process and open the Process Manager, terminate the activity, then terminate the workflow
OOTB means "out of the box." Assuming no customizations in the way, I would expect WC to terminate the running process if you delete the primary business object. Maybe it doesn't? Maybe it doesn't for change objects?