Fixed!

Issue was with AI error - it suggested GPRMC as sequence to wait, but in real life it is GNRMC.
Fixed it and everything works fine, even with software serial.