So since people still seem to come around here looking for an answer (I don't blame you, it's a good mouse), I decided to do some copy-pasting from my MX Anywhere 2 answer. Anyway, enjoy:
UPDATE FOR >15.10:
In my original answer I said that the problem would most likely be fixed when 15.10 comes around. While 15.10 does indeed have bluez 5, there is still some problem with pairing. Honestly, it was quite a while since I fixed this problem myself, but if I remember correctly, the MX Master (MX Anywhere 2) uses a PIN-less pairing method which isn't quite properly implemented yet in Ubuntu. Here are some commands which you can use as a quick fix:
hciconfig hci0 sspmode 1
hciconfig hci0 down
hciconfig hci0 up
If you're using another Bluetooth device than hci0, you obviously have to change that part of the commands, otherwise, they should be good to go.
ORIGINAL ANSWER (for < 15.10):
I had this problem a while back. Basically what's happening is that the MX Master requires Bluetooth Smart and Ubuntu ships with bluez (the Bluetooth driver) 4 which does not have support for Bluetooth Smart. Bluez 5, which adds support for Bluetooth Smart, is supposed to start shipping with 15.10, but for now, you'll have to install bluez 5 manually if you want to use it.
Just a heads up, if you want to have a stable system, DON'T DO THIS. First of all, this will break the built in Bluetooth control in the settings panel. This method that I'm about to describe adds a PPA too, which is supposed to be bad for your system when upgrading and stuff. Only do this if you know how to remove a PPA and revert to bluez 4 or if you just don't care and want to get it working. ;P
First, you need to add a PPA with bluez 5. I would recommend the bluez 5 PPA made by Austin since that's the one I have used before. Add it with this command:
sudo add-apt-repository ppa:vidplace7/bluez5
Then refresh apt-get:
sudo apt-get update
After that you can install bluez 5 with this command:
sudo apt-get install bluez
Now that you have bluez 5, you need a way of controlling Bluetooth since, as stated earlier, the built in control panel will not work anymore.
There are two ways which I have tried for this. If you want to have a GUI then Blueman is your best option. You can install it simply with:
sudo apt-get install blueman
This will install the Blueman Bluetooth interface which you can open for your app launcher. It should be straight forward to use and not require any in depth explanation.
The method I recommend however is to use the command line. I found this to be much more stable (worked on login screen while Blueman didn't) and actually surprisingly intuitive to use for being a command line.
The way it works is that you type bluetoothctl in to the command line where you'll now have a command interface to interact with Bluetooth devices. You can type help to get a list of commands and what they do. The command that you'll want to use first for pairing the MX Master is the scan command. If you type scan on, your computer will start searching for Bluetooth devices. While in this mode, put your MX Master in to pairing mode and wait for it to show up in the console. It will show up something like this:
[NEW] Device XX:XX:XX:XX:XX:XX MX Master
The "XX:XX:XX:XX:XX:XX" string is the MAC address of your MX Master. To pair it and connect it, type:
pair XX:XX:XX:XX:XX:XX
connect XX:XX:XX:XX:XX:XX
Make sure to change all the "XX:XX:XX:XX:XX:XX" to the MAC address you got when scanning.
And that should about do it. Hope it works for you!
Best Answer
There are two ways to pair Logitech unifying mice/keyboards.
If you have Windows (in a dual-boot configuration) you can install the Logitech Unifying Software and the Logitech Mouse software, and pair/configure them in Windows. See https://support.logitech.com/en_us/product/marathon-mouse-m705/downloads#windowsPnlBar. All settings made in Windows will carry over to the Ubuntu environment.
In Ubuntu, you can install Solaar to do many, but not all, of the same pair/configure actions. Solaar is in the Ubuntu repositories (via Synaptic), or can be found at http://pwr.github.io/Solaar/ or https://github.com/pwr/Solaar. The github versions may be newer.