I sent a bug report with some logs to the kernel-bluetooth mailing list:
We did not yet pinpoint the problem, but it helps to pair the mouse not with the GUI but with bluetoothctl instead.
Start pairing on the device, then:
bluetoothctl
# scan on
[NEW] Device XX:XX:XX:XX:XX:XX your device
# scan off
# pair <XX:XX:XX:XX:XX:XX>
Fill in the correct address of the device you want to use.
This does survive a reboot, though it still disconnects for a few seconds while in use. It will reconnect itself after a few seconds though.