When my phone(Android 6) and Laptop (Windows 10) are connected to same wifi network KDEConnect work flawlessly, But when I connect my laptop to phone's hotspot for internet these devices are not able to connect through KDEConnect. Sometimes it won't sometimes it will. How to solve this issue?

I periodically experience a similar if not the same issue that you are describing. After some investigation, it seems to have to do with the phone being assigned an IP address either a IPv6 or some esoteric address like 192.168.237.69 or the such. Unfortunately it hot spot does not seem to allow a dedicated IP or one that stays within a certain range of numbers to work with. Sort of like shooting at a moving target for addressing your other devices. I wish you good luck with this and if I do find any resolution or further, I will certainly pass it along here for you.

Cheers,

SanDiegoBeck