Location needs to be enabled for Bluetooth Low Energy Scanning on Android 6.0

No, this is not a bug.

This issue was brought up to Google where they responded saying that this was the intended behavior and they won't fix it. They directed developers to this site where it points out that location permission is now needed for hardware identifier access. It is now the developer's responsibility to make their users aware of the requirement.

In the issue, however, it doesn't address why Location services (GPS, etc.) are required and it doesn't seem like they are going to revisit the issue to explain this since it has been marked as the intended behavior.

To answer the second part of the question: Yes, it is possible to scan without enabling Location services. You can do a Bluetooth classic scan using BluetoothAdapter.getDefaultAdapter().startDiscovery() and that will work with Location services off. This will discover all Bluetooth devices, BLE and otherwise. However, BLE devices won't have a scan record that they would have had if they were seen as a result of startScan().

I solved this by setting targetSdkVersion to 22 in the Gradle file.You must declare ACCESS_COARSE_LOCATION in the manifest but, BLE scanning will work even if the user denies this permission from App Settings.

This is just a hack to avoid requesting location permission. It's better to target the latest android versions.

Edit

This solution should no longer be used as Google Play will require that new apps target at least Android 8.0 (API level 26). Apps should request for location permission for BLE scanning.

What I found is that after Android 6 you must grant ACCESS_COARSE_LOCATION permission. But on some devices is also necessary your phone location service (GPS) to be switched on, so you can discover peripheral devices. I found that using Nexus 5x, with Android 7.0.