I realized that Android M requires at least one of ACCESS_COARSE_LOCATION and ACCESS_FINE_LOCATION permissions to scan Wifi.
I don't think it's a technical issue but that there is a sort of philosophical reason (e.g., privacy) for such a weird policy.
But I couldn't find the exact reason for that and I would appreciate if someone give the answer.
The list of available Wifi networks for a device can be indeed used to locate the device.
To locate the device on needs the list of of the wifi networks the device can see and a huge database with known wifi networks and the position of the access points. With this information one can triangulate the position of the phone.
Multiple of these huge databases exist. Apple, Google, etc. have each one and there are also public ones: http://www.openwlanmap.org/
Read more about it here: https://en.wikipedia.org/wiki/Wi-Fi_positioning_system