Thanks for confirming those are the correct steps Joshua - I was in transit and couldn't respond.
A couple more things to consider before you take this approach.
Are all of the records you are deleing in SFDC, Leads? If so, you will lose any related lists associated with each Lead (e.g. Tasks, Activity History) that exist on your Salesforce leads. If there are SFDC Contacts, I would not take this approach as all the leads in Marketo will synch back as SFDC Leads.
How did your 10K leads that are in SFDC get into Marketo? If they were initially synched from SFDC, they you should have the Activity History synched into the Marketo leads. Otherwise, you will not have this history anywhere.