The difference could be that not all leads are inside a list and that not all leads are still subscribed and able to receive your emails.
I would try in the smart list the following:
Unsubscribed = false
Email invalid = false
Email address = "is not empty"
Marketing suspended = false
This will give you a more accurate picture of your mailable leads and will potentially run a lot faster than "member of all lists"