You have to buile up a sorta relationship with Yojimbo.
First off, When you go to buy the fayth, Tell him you want to "Defeat the most powerful of enimies", he will then ask for 250,000 gill. Pay him 750,000 (three times the asking rate) to gain his favor and a strength sphere. if you can afford more, then give it. Now summon him in random battles against smaller fiends. Pay a minimum of 250,000 each time and he should use Zanmato. After a while though, he'll expect a raise in salary, so don't use him more than 10 times in random fights. Every time he Uses Zanmato in battle, he will like/trust you more and will be more likely to do it for the same price or less next time. If he likes you enough, sometimes he will use Zanmato as soon as he is summoned without even having to be paid!
But beware, should he have to attack with his dog Daigoro, or if he falls in battle, his feelings towards you will decrease, making it less likely that you will see him use zanmato.