SugarCRM Web Service API provide only methods for Set and Get entries/relationships.
How can I do delete/remove entries and their relationships with entries in other related modules?
Is the Web Service API designed only for Get and Set?
You can set the 'deleted' flag to '1' as one of the fields in the 'name_value_list' in the set_entry/set_entries call and it will mark a record deleted.
http://gist.github.com/4019840
For relationships, you can use set_relationship/set_relationships and pass the argument '1' for the 7th argument to that call will delete the relationships instead of add them.