First off, please vote for the idea: Access Storage Used per Record Type information through the API
The short answer would be that no, you can't get the same information directly via the SOAP API.
Trying to get the counts via a SOQL query will be problematic as the number of records goes past the governor limits (50,000 records I think). If you do hit the limit in a query you will get the OPERATION_TOO_LARGE error back.
The reason for this, as given by Salesforce:
The query has returned too many results. Some queries, for example those on objects that use a polymorphic foreign key like Task (or Note in your case), if run by a user without the "View All Data" permission, would require sharing rule checking if many records were returned. Such queries return this exception because the operation requires too many resources. To correct, add filters to the query to narrow the scope, or use filters such as date ranges to break the query up into a series of smaller queries.
In your case a count() query is the same as returning every record at the DB level so if your count returns > 20K records then it is really the same as returning all that data from the DB perspective. After all, the access grants still have to be calculated to return an accurate count. [Source]
There is currently no Partner API call that will allow you to run multiple SOQL queries in one go.
If you are prepared to get your hands a bit dirty and accept the associated risks you could screen scrape the data off the page. The risks being that it isn't supported by Salesforce and could easily break if they make changes to the page.
The URL would be something like:
https://<instance>.salesforce.com/setup/org/orgstorageusage.jsp?id=<Your Org Id>
At the time of writing the key prefix appears in the class for the span containing the sObject label. This should be unique(mostly).
The keyPrefix should match up with the DescribeGlobalSObjectResult.keyPrefix.
How is the size of an individual record determined?
I was going to suggest adding up all the byteLength values from DescribeSObjectResult.
This will get you close, but for some data types the value isn't populated (boolean).
Turns out I was way off with this. @ca_peterson points out in the comments that the record size is fixed by Salesforce based on the record type. The addition of custom fields makes no difference. See What are the various record sizes? This seems counter-intuitive coming from a SQL Server background, but it is right there in the docs.
How salesforce is able to show the information in storage usage page without storing it anywhere / calculating it dynamically without any problems?
They don't have to play by the same rules we do. With direct access to the underlying database they could perform queries without limits or sharing rules. They may maintain any number of additional structures to track usage. It is hard to say when dealing with a black box.
As of Spring `15 there is the Limits Resource in the REST API. Unfortunately this currently doesn't give the storage breakdown by object type. Only an org wide overview.