Deleting records is usually not a very good solution as it means that you will discard activities.
Now, there are situations where you might not have a choice.
You need to isolate couples of records where one is a lead and the other is a contact. This is not really easy to do in Marketo, so I would suggest that you extract the list of leads from Marketo, including the SFDC Type field, then I would do some computations in Excel to isolate the appropriate records.
One thing I do is to create a field names Mkto ID and a smart campaign that copies the real Marketo ID in this field each time a new lead is created. The interest of this is that this custom Mkto ID field can be exported.
Once I have done all this I create a smart list which filter is Mkto ID is [List of IDs identified in Excel]. This will be the list of leads to delete.
Tripple check it before you delete them, though, as there is no undo on delete
Thank you for your comments, I will test the above process and get back to you in case of any queries.