I tend to believe he got Dragonbinder from Pree and the warlocks. I suppose it was their "weapon" of some sort, being magical and all, to try and exact revenge against Daenerys. When Euron captured them, he also learned of the horn and its power.
About the FM, I still think the hypothesis of him paying them with the dragon egg he allegedly had (instead of throwing it into the water) is a plausible explanation. Don't think they'd "work" with someone.