Why on earth is my Garmin connect app forcing me to keep location service (on accurate level!) on to keep my Fenix 3 HR connected to my phone?!? Maybe you have realized that the GPS sucks at the watch itself and have to track me via phone? No matter what is the reason, this is certainly not something I accepted when I purchased my watch... So I would suggest you to either give me full refund for my watch (yes that is practically the only feature that actually works on this device) or patch your app so that it won't need the permission.
To update my situation with this.
After some research I couldn't find the exact mention from google/android that this is a Marshmallow feature (although I found stackoverflow threads complaining about this same issue). However I am willing to believe this is a Marshmallow "feature", so maybe I should be whining on Android forums then... However this does not change the fact that everything worked before the update on GC, and that is just a fact that Garmin has some tools to work with.
I however have come up with a workaround with this problem (at least on CM 13). If I disable location from privacy settings for all google service and other google products then I am able to set the location on "device only" and GC connects to my watch. I really don't know if that really disables the location services or not, but at least the pin icon won't appear any more. I also don't know if this will lead into other issues on other apps. I have noticed that some apps crashes instantly while this setting is enabled, but those aren't that important to me so I guess this is just the price to pay.