It's an issue with Marshmallow and the GPS. If you google Marshmallow GPS Not Working you will find a link to Issue 190376 under Android's Issue Tracker where hundreds of people with phones using the Marshmallow update having this same issue.
I'm also having this issue after upgrading to Marshmallow and will most likely be re-downing the Lollipop firmware from June 4th and downgrading. I had no issues on Lollipop, only after upgrading. I also did as much troubleshooting as I could including factory resetting my phone.
TL;DR It's a known Google issue. No ETA on them fixing it.