The pairing function f(a,b) = (a + b)(a + b + 1)/2 + a is the one that arises by drawing diagonals on the natural number lattice, and marching down them from upper left to lower right. See the picture here.
To compute f(a,b), one needs to perform some additions and a multiplication, which seems to be quadratic time in the length of a and b, that is, in log(a)+log(b), which would seem to be constant time in max(a,b), but I'm not sure if this would be what you meant.
In that book, it is noted that Polya has proved that any surjective polynomial pairing function is equal to this function or to its dual form f(b,a). (And someone gave a talk here at CUNY a few weeks ago on precisely this fact.) So if this function is not acceptable to you, then you will find no polynomial surjective function.