Slowest many-one reduction? When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. In this context we do not need a tight bound on the running time of the reduction. It suffices to have any polynomial bound, allowing that it may possibly have a very high degree. 

Nevertheless, for natural problems, the bound is typically a low degree polynomial (let us define low as something in the single digits). I do not claim that this must always be the case, but I am not aware of a counterexample. 

Question: Is there a counterexample? That would be a polytime computable many-one reduction between two natural $NP$-complete problems, such that no no faster reduction is known for the same case, and the best known polynomial running time bound  is a high degree polynomial. 

Note: Large, or even huge, exponents are occasionally needed for natural problems in $P$, see 
Polynomial-time algorithms with huge exponent/constant. I wonder if the same also occurs in reductions among natural problems?
Allender suggests the answer is no:


  There seems to be no pair of natural NP-complete problems A and B known, where a reduction from A to B is known to require more than linear time (even under the assumption that P $\ne$ NP)


Reference:

E. Allender and M. Koucký, Amplifying lower bounds by means of self-reducibility. Journal of the ACM 57, 3, Article 14 (March 2010).