update
Google's official response to your question:
Hi,
We understand you have query on particular usage which can be looked up here in stackoverflow.
https://stackoverflow.com/questions/14812326/android-bluetooth-get-uuids-of-discovered-devices
Thanks
In Android 6.0 there are changes to permissions. Introducing runtime permissions, rather than a global acceptance of all app required permission upon installation of the app.
In a nutshell, permissions types are loosely put into two types, normal or dangerous. Any permission that encroaches upon a user's privacy is regarded as dangerous.
Permissions are also placed into groups of similar permissions, example access fine location and coarse location.
Users are given a choice whilst using the app to accept the permission of a particular group that is regarded as dangerous. Once the permission for a particular group is given for that app run, it is not asked again for permissions from within the same group, but will be asked for permissions from other groups as required.
See details below:
Runtime permisssions.
This release introduces a new permissions model, where users can now directly manage app permissions at runtime. This model gives users improved visibility and control over permissions, while streamlining the installation and auto-update processes for app developers. Users can grant or revoke permissions individually for installed apps.
On your apps that target Android 6.0 (API level 23) or higher, make sure to check for and request permissions at runtime. To determine if your app has been granted a permission, call the new checkSelfPermission() method. To request a permission, call the new requestPermissions() method. Even if your app is not targeting Android 6.0 (API level 23), you should test your app under the new permissions model.
.../
Beginning with Android 6.0 (API level 23), users grant and revoke app permissions at run time, instead of doing so when they install the app. As a result, you'll have to test your app under a wider range of conditions. Prior to Android 6.0, you could reasonably assume that if your app is running at all, it has all the permissions it declares in the app manifest. Under the new permissions model, you can no longer make that assumption.
Permissions are classed as normal or dangerous
Bluetooth access is regarded as a normal permission, whilst pairing or reading details of an app is regarded as dangerous.
Dangerous permissions cover areas where the app wants data or resources that involve the user's private information, or could potentially affect the user's stored data or the operation of other apps. For example, the ability to read the user's contacts is a dangerous permission. If an app declares that it needs a dangerous permission, the user has to explicitly grant the permission to the app.
So when requesting information from a device:
If an app requests a dangerous permission listed in its manifest, and the app does not currently have any permissions in the permission group, the system shows a dialog box to the user describing the permission group that the app wants access to. The dialog box does not describe the specific permission within that group. For example, if an app requests the READ_CONTACTS permission, the system dialog box just says the app needs access to the device's contacts. If the user grants approval, the system gives the app just the permission it requested.
See Working With System Permissions for details of implementation.
edit In response to your- comment
There are multiple issues with bluetooth bugs and the release of android 6.0. as there was with 5.0, it is anticipated these will be fixed with the next patch. However, I don't see your issue as a bug.
And after seeing your post here on google, my answer directly answers what your are perceiving as a bug.
Your screen shot:

And from your code here on github:
android {
compileSdkVersion 23
buildToolsVersion "23.0.1"
defaultConfig {
applicationId "me.bluetoothuuidsample"
minSdkVersion 18
targetSdkVersion 23
versionCode 1
versionName "1.0"
}
The marshmallow devices are behaving exactly as they are intended to with runtime permissions, but I am sure google will confirm this for you.
To prevent having to deal with the changeover at this stage, use the target sdk as less than 23.
targetSdkVersion 22
This Cheesefactory blog goes into detail well. Everything every Android Developer must know about new Android's Runtime Permission
edit 2
Fetching UUIDs requires location permission, there's a post here that's goes into more details: https://stackoverflow.com/a/33045489/3956566