Given a real polynomial $p(x) = \sum_{i=0}^n c_i x^i $ of degree $n$ on the interval [-1,1]. I would like to find bounds $a$ and $b$ such that
$$ a < p(x) < b \textrm{ for } x \in [-1,1] $$
I would like to find the bounds without determining the actual extrema of $p(x)$ (finding the zeros of $p'(x)$ and so on) as $n$ is large between $10^6$ and $10^7$. I am specifically interested in numerical methods where I can trade-off bound accuracy and computational complexity. For example, a simple bound is given by $\sum_{i=0}^n |c_i| $. Optionally, $p(x)$ is given in terms of Chebychev polynomials.
Computing coefficients for a Chebyshev or Bernstein basis has cost $O(n^2)$, these give reasonable enclosures for the range of function values.
I interpret your question as the task to find non-trivial bounds on the range in complexity $O(n)$. One possibility is to find the following characteristics of the coefficient sequence \begin{align} C_{e,p}&=\sum_{m:c_{2m}>0} c_{2m}\tag{even index, positive coefficient}\\ C_{e,n}&=-\sum_{m:c_{2m}<0}c_{2m}\tag{even index, negative coefficient}\\ C_{o,p}&=\sum_{m:c_{2m+1}>0} c_{2m+1}\tag{odd index, positive coefficient}\\ C_{o,n}&=-\sum_{m:c_{2m+1}<0} c_{2m+1}\tag{odd index, negative coefficient}\\ \end{align} Then we know that the range over $[0,1]$ is contained in $[-C_{e,n}-C_{o,n},C_{e,p}+C_{o,p}]$, and over $[-1,0]$ in $[-C_{e,n}-C_{o,p}, C_{e,p}+C_{o,n}]$. A bound on the values over $[-1,1]$ is thus $$ |p(x)|\le M=\max\{C_{e,n}+C_{o,n},\,C_{e,p}+C_{o,p},\,C_{e,n}+C_{o,p},\, C_{e,p}+C_{o,n}\}, $$ or as separate upper and lower bounds $$ -C_{e,n}-\max(C_{o,n},\,C_{o,p})\le p(x)\le C_{e,p}+\max(C_{o,n},C_{o,p}). $$ Essentially this is the result of a direct application of an interval evaluation for the interval $[-1,1]$ to the monomial representation of the polynomial. Using the Horner scheme for the evaluation not only reduces the effort but might also result in tighter bounds. Another way for a refinement is to use a fixed sub-division of the interval and combination of the results of the interval evaluations for every subinterval.