After a few hours of hit and trial, found this solution which addresses the issue. The answer to the original question is still unknown i.e. I haven't found out how to add an app larger than 100 MB. But I have found a solution to why the app was more than 100 MB in the first place. Sharing it so it may help others like me who are beginning with React SPFX development.
Issue
My project has absolutely zero media files (no images, no videos). So it was baffling that the package was more than 100 MB. I had more than 25 components and 5 web parts though. I usually start my workbench (using Gulp Serve) and keep on making changes until it's ready for build. I then stop Gulp Serve and run my build commands (Gulp Bundle -ship & Gulp Package-Solution --Ship). What it does is increment the size of the .sppkg file with each build. It also adds a painful amount of delay in uploading and checking the app to app store (almost 10 minutes in the worst case scenario). And then when the package crosses 100 MB, you can't update it in your site collection any more.
Solution
I stumbled upon "Gulp Clean" by chance and thought to give it a try. I ran it before my build commands and voila! The package which was 100 MB just a few minutes back was now 1.3 MB (obviously since all that my solution contains are .ts, .tsx and .scss files). Now updating my app in app store takes less than a minute.
So I created a bat file to build my package every time I need to. The contents of the bat file is as shown below:
call gulp clean
call gulp bundle -ship
call gulp package-solution --ship
Additional Reference
I found this post from Waldek Mastykarz too late. Although the reasons for using "Clean" in his post were different than mine, it would have saved me a few hours if I had just seen this a little early.
Warning
I am still discovering Gulp Clean in detail and can't say for sure if it has no side effects.