Thankfully Apple AppStore provides a nice index to look up all the apps. All the apps have been categorized into 23 broad categories. Within each category the apps have been indexed alphabetically. So, to discover all the apps in the iTunes AppStore, one only needs to crawl the main index page, find all the category pages and then crawl the category alphabetical index.
The main index page of iTunes AppStore is at – https://itunes.apple.com/us/genre/ios/id36?mt=8.
From the main index page, one can get all url’s that match the regex: “^https://itunes.apple.com/us/genre/”. Category pages all have the url structure – https://itunes.apple.com/us/genre/ios-<category-name>/<category-id>?mt=8. For example, the apps categorized under Entertainment can be found at: https://itunes.apple.com/us/genre/ios-entertainment/id6016?mt=8.
In fact, one need not crawl the category page at all. The category page is alphabetically indexed, each alphabet page having the url structure: https://itunes.apple.com/us/genre/ios-<category-name>/<category-id>?mt=8&letter=<alphabet>&page=<page-number>. An example page being: https://itunes.apple.com/us/genre/ios-education/id6017?mt=8&letter=G&page=6.
I was able to discover 700K apps approximately! The script below also crawls each app page to extract information about the app.