Understanding Leads API in Marketo

We are just beginning to test some tools to get data out of Marketo into our data warehouse. For that, we are using a third party tool. One of the tables (a Marketo system table) I see created is a "lead" table.

It's not a "table". It's the response from a REST API endpoint. The decision to present it as a relational "table" is entirely up to the consuming application (and often an incorrect use of the RDBMS concept).

Is this table all the contacts (with email/without email/unsubscribed/marketable leads etc) that I have in my Marketo instance?

Depends on the 3rd-party tool and whether that application applies filters to the result set. Most likely, it is indeed supposed to be all People/Leads in your Marketo instance (Marketo doesn't use the word "Contact"; all instances use "Lead" in some places and newer instances use "People" as well).

Again, this is not a table. The REST API does not return tables. It returns JSON-, CSV- and/or PHP-serialized data.

I tried to read the documentation on Leads API but it was difficult for me to follow since we are relatively new to Marketo.

You need to ask the 3rd-party vendor. The filtering (and therefore the count) in a 3rd-party application is entirely under their control. It's likely that they (a) are not reconciling deleted leads and/or (b) did not fetch all the leads from your Marketo instance. It's extremely easy to introduce such discrepancies if the product has not been meticulously designed to avoid them.