If Windows is installed in UEFI mode then it shouldn't boot in Legacy mode. But I am not completely surprised. I have heard things like that before.
It's good that Windows works. I would keep Windows and shrink the Windows partition. But the Ubuntu MATE installation might become a little trickier if you decide to keep Windows.
If you install in Legacy mode just install GRUB to MBR (sda) and it should find both Windows and Ubuntu MATE.