Yes 2,000,000 Gil is too much to offer to any fiend. It is more of a fiscal advantage to offer about 20 times the HP of the creature and if that doesn't work keep bribing about 10,000 to 50,000 more at a time depending on how many HP the fiend has. Bribing is cumulative to a fiend. So if you bribe 200,000 and miss try offering about 20,000 more or so until it works.
If you bribe an amount that you know has worked before and it misses this time, you can simply bribe 100 Gil until it works.