Change the contact type on all relationship records from the one to delete to another one. If running a globally change, you must run two global changes: one for Individual/Contact/Employee Relationships and one for Org/Business Relationship