I've got hundreds of thousands of leads needing to be deleted from Marketo (long story, don't ask). I know this will tax SFDC API calls if I choose to delete them from there also, and don't stagger it, but I was curious if such a bulk delete would cause any problems with the Marketo instance?
You are correct that it will tax your SFDC API limit without throttling.
This should not cause any major issues with the Marketo instance, but might yield slight delays to your day to day programs. Advise doing this on the weekends or periods when the activity in your own instance might be less.
You can view a log of current activities and the amount of traffic Marketo is processing by going to Marketing Activities > Campaign Queue.
My only question is that are all of the spare leads that are bad in Salesforce? I know we have a lot that are not in Salesforce. So,if they aren't, you can delete them and have remove from SFDC = false and that won't hurt your API calls.