Thanks to @oldfred for suggesting the boot-repair approach!

So I went about it the following way:

1. I enabled UEFI (But disabled the "Secure Boot" option as it is an essential step for the boot-repair tool to work)


2. Booted through my Ubuntu 18.04 USB by pressing "F12" at startup


3. Selected the "Try Ubuntu" option and installed Boot Repair


4. Ran the utility by typing boot-repair in the terminal


5. Clicked on "Advanced Options" and checked the option "Backup and rename Windows EFI files" under the tab "Main Options" and clicked on "Apply"


6. Kept an eye on the progress of the tool and performed whatever steps it may asked of me while it was working it's magic


7. Hopefully at reboot you will be able to access both the operating systems through Grub bootloader


8. If you are still being directed to the Windows Boot Manager during the boot, please change boot order of UEFI, making the newly added boot manager to load up first compared to your original Windows Boot Manager. Sometimes the new Boot Manager might have the same name, but don't freak out, just switch the order, there should be only two entries there.

UPDATE 1 : Most of the tutorials will ask you to click the "Recommended repair" option when you open the boot-repair tool but please do not do that. Follow the steps that I have written above. This is because sometimes the boot loader repair process fails (also failed in my case) and the utility ends up adding various entries, for loading up Windows, in the grub boot menu, none of which works. Thankfully I had enabled the "Backup and rename Windows EFI files" in the boot-repair tool which ended up adding an extra "Windows bkpbootmgr" entry in the grub boot menu, which of course is the backup of the original windows boot manager, which actually works. The "ubuntu" entry in the grub boot menu will of course work fine :)

UPDATE 2 : You can install and use a tool like grub-customizer to remove all the Windows entries which do not work keeping only the one which works.

UPDATE 3 : I installed Ubuntu in legacy mode first and then I tried to fix the grub efi issue using boot-loader. This may seem like an overkill but it will give you some room to make mistakes since you can't mess up your original UEFI bootloader when you are in legacy mode. boot-repair is actually a great tool which will help you uninstall grub-pc and install grub-uefi while you are running the fix. Just make sure that you know where your boot manager partitions are.