Try going to Maps > Settings > Location Settings and turn off "Report from this Device", "Enable Location Sharing", "Automatic Check-Ins", and "Enable Location History".
If that doesn't work. Try rebooting. Then try uninstalling updates on Maps, and reboot, and then install updates for Maps again.
Remember that you need to charge the battery up to at least 90% in order to reset the battery history. (At least on the s3. I bet it's the same for the S4.)
If you can briefly plug it in and unplug it to reset the battery history, then press the refresh button every second, see when the Maps app pops up with the usage %. Then quickly go to the application manager in Settings and look at the "Running" tab. Then click on the Maps application and at the bottom you can see the "Main Process in use". Tell us what you find so we can better help.
Also, I suggest purchasing and installing Better Battery Stats from the play store for this kind of stuff.