A male main character was genetically engineered, had gills in his throat, and was an executioner in a post-apocalyptic world. He was able to move long distances instantly through something called the bine toad.
This is a long shot, but could the book be The Marked Man by Charles Ingrid (aka Rhondi A. Vilott Salsitz).
It's set in a world where technology used for genetic engineering has gone wrong and caused a plague that wiped out most humans and left the remainder genetic freaks. The protagonist is Thomas Blade, who does have gills and is an executioner.
Blade can travel long distances on the Ghost Road, so this vaguely matches your description, but there is no mention of a bine toad.
The book was published in 1989 so it's in your date range.