Or you could defeat them both in matter of seconds by letting Yojimbo unleash his Zanmato. It takes less time to gather the required amount of money (Omega Ruins) than leveling up as mentioned, even though it's a very good strategy.
And personally, even when i had Yojimbo on low levels, 4 million (yes) gil should be enough for Yojimbos random meter to result in a Zanmato. Otherwise just reset and try again. If you've leveled him good through out the game, you won't need as much.
