Mass change Leads Status

@PvanderValk correct, deleting a record (leads) does not delete associated records (contacts).

You could delete leads from the prospecting workspace by ticking the box in the top left corner and then clicking delete: