Hi Tricia, Liz,
We have similar process with restricting SFDC leads accessibility to Marketo user, using Lead Sharing rules.
To delete SFDC leads from Marketo, you need to first run 'Change Owner' lead action in Marketo to change the owner for those leads to Marketo user. Then you should be able to delete those leads.