I'm relying on Microsoft's framework to initialize the connection between the two devices and I just respond when it either tells me the devices are connected or if they failed to connect. So I don't really have any insight as to why you are seeing so many issues with the connection. I don't think it's normal for it take 20 attempts to make a connection though. I've tested connecting my Surface Pro 4 to my Android tablet and it usually just takes a few seconds to get everything connected. I can try to run some tests with connecting my laptop to my tablet to see if it works any differently.
UPDATE:
It took about 30 seconds to pair my surface pro 4 to my laptop, then I went into MobileSheets, set up the Surface Pro 4 as the leader, connected to it from the laptop and it took a few seconds for this and then worked just fine. I then closed MobileSheets, restarted it on both devices, ran the test again, and once again, it just took a few seconds to connect the devices and get everything configured. I could then load songs and turn pages without issue.
Mike
UPDATE:
It took about 30 seconds to pair my surface pro 4 to my laptop, then I went into MobileSheets, set up the Surface Pro 4 as the leader, connected to it from the laptop and it took a few seconds for this and then worked just fine. I then closed MobileSheets, restarted it on both devices, ran the test again, and once again, it just took a few seconds to connect the devices and get everything configured. I could then load songs and turn pages without issue.
Mike