See this clear description here:
https://community.marketo.com/MarketoDiscussionDetail?id=90650000000PNRQAA4
"Lead Was Deleted From SFDC" allows you to add the constraint of a date and/or a minimum number of times. This is more of an activity filter - how many leads were deleted in SFDC between August 1 and August 14?SFDC Deleted Is True means the lead was deleted in the CRM by Marketo or by SFDC. So this tells you who was deleted for all time.
You may be getting different numbers because of the loss of Activity data after 90 days or because of the contraints you are using.
https://community.marketo.com/MarketoArticle?id=kA050000000L3hzCAC
Flow Action: Delete Lead from SFDC
https://community.marketo.com/MarketoArticle?id=kA050000000LAB1CAO