Is there a cubic or quartic approximation for these data points; $$(0,1000000), (1000000, 100), (10000000, 10)$$ whilst also ensuring that no point from $$1000000 < x < 10000000$$ is greater than |100|?
I can currently fit the data points successfully with a cubic but have no Idea how to enforce the upper bound restriction on the function.
On
I think the answer is no, but I'm unsure how to prove it.
Let $$ g(y) := f(y * 1e6) / 10 $$ Then your problem is equivalent to asking if there is a degree 4 polynomial $g$ where $$ g(0) = 1e5, g(1) = 10, g(10) = 1 $$ and $\text{abs}(g(x)) \leq 10 $ for $x \in \left[1,10\right]$.
The interpolation problem has a unique solution in degree 2 and infinitely many solutions in degree 3 and 4.
However, even with 2 extra degrees of freedom, the scaling in the first term means that $g$ will be very "wavy" between 1 and 10. See for example this lagrange interpolation in sagemath:
(you can fiddle with different constants in your own environment -- the graph ends up roughly the same.)
This is not even close to your desired bounds.
In terms of actually showing that any interpolation fails your bounds, I think you could prove it by looking at the local maximum/minimum in the longest interval between 1 and 10 where there are no roots. Since the degree is bounded, this interval has length at least 3. $g$ probably jumps to some value greater than 10 in that interval.
You can fit the three data points with a quadratic polynomial. You don't need a cubic for that step. If you use a quadratic polynomial $f(x),$ then you will have $f(x) \leq \lvert 100 \rvert = 100$ for all $x \in (10^6, 10^7)$ (that is, for all $x$ such that $1\,000\,000 < x < 10\,000\,000$). That satisfies the requirement that you literally wrote, that the value can't be greater than $\lvert 100 \rvert.$
But the value of $f(5\,500\,000)$ will be very negative.
I suppose the reason you are having difficulty is that you actually want to have $\lvert f(x)\rvert \leq 100$ for $x \in (10^6, 10^7)$, not $f(x) \leq \lvert 100 \rvert.$ So $\lvert f(x)\rvert \leq 100$ is the requirement I assume in this answer.
Let $f(x)$ be your desired polynomial. You require that $-100 \leq f(x) \leq 100$ for $10^6 < x < 10^7.$
Consider $f(a),$ and $f(a + 5\times10^5)$ where $10^6 \leq a \leq 9.5\times10^6.$ By the Mean Value Theorem (MVT) there must be a number $a_1$ in the interval $(a, a + 5\times10^5)$ such that $$ f'(a_1) = \frac{f(a + 5\times10^5) - f(a)}{(a + 5\times10^5) - a} = \frac{f(a + 5\times10^5) - f(a)}{5\times10^5}. $$ But according to your requirements, we must have $-100 \leq f(a) \leq 100$ and $-100 \leq f(a + 5\times10^5) \leq 100.$ So $$ \frac{-100 - 100}{5\times10^5} \leq \frac{f(a + 5\times10^5) - f(a)}{5\times10^5} \leq \frac{100 - (-100)}{5\times10^5}, $$ or more simply, $$ -0.0004 \leq f'(a_1) \leq 0.0004 . $$
Now apply this fact to the two consecutive intervals $(b, b + 5\times10^5)$ and $(b + 10^6, b + 1.5\times10^6)$ where $10^6 \leq b \leq 8.5\times10^6.$ According to the previous result, there exist numbers $b_1 \in (b, b + 5\times10^5)$ and $b_2 \in (b + 10^6, b + 1.5\times10^6)$ such that $ -0.0004 \leq f'(b_1) \leq 0.0004 $ and $ -0.0004 \leq f'(b_2) \leq 0.0004. $ The MVT now tells us that for some number $b_3 \in (b_1, b_2),$ $$ f''(b_3) = \frac{f(b_2) - f(b_1)}{b_2 - b_1}. $$ But from $ -0.0004 \leq f'(b_1) \leq 0.0004 $ and $ -0.0004 \leq f'(b_2) \leq 0.0004 $ we get $$ \frac{-0.0004 - 0.0004}{b_2 - b_1} \leq \frac{f(b_2) - f(b_1)}{b_2 - b_1} \leq \frac{0.0004 - (- 0.0004)}{b_2 - b_1}, $$ that is, $$ \frac{-0.0008}{b_2 - b_1} \leq f''(b_3) \leq \frac{0.0008}{b_2 - b_1}. $$ But since $b_1 < b + 5\times10^5$ and $b_2 > b + 10^6,$ we know that $b_2 - b_1 > 5\times10^5$ and therefore $$ -1.6 \times 10^{-11} < f''(b_3) < 1.6 \times 10^{-11} $$ for some number $b_3$ in the interval $(b, b + 1.5 \times 10^6),$ that is, in some subinterval of width $(1.5 \times 10^6)$ within the interval $(10^6, 10^7).$
Now for $10^6 \leq c \leq 6 \times 10^6,$ consider the intervals $(c, c + 1.5 \times 10^6)$ and $(c + 2.5 \times 10^6, c + 4 \times 10^6),$ two subintervals of width $(1.5 \times 10^6)$ within the interval $(10^6, 10^7).$ From the previous result we know there is a number $c_1 \in (c, c + 1.5 \times 10^6)$ and a number $c_2 \in (c + 2.5 \times 10^6, c + 4 \times 10^6)$ such that $ -1.6 \times 10^{-11} < f'(c_1) < 1.6 \times 10^{-11} $ and $ -1.6 \times 10^{-11} < f'(c_2) < 1.6 \times 10^{-11}. $ We apply the MVT again -- by now you should see the pattern and be able to fill in the steps -- to conclude that $$ \frac{-3.2 \times 10^{-11}}{c_2 - c_1} < f'''(c_3) < \frac{3.2 \times 10^{-11}}{c_2 - c_1}, $$ and since $c_2 - c_1 > 10^6,$ $$ -3.2 \times 10^{-17} < f'''(c_3) < 3.2 \times 10^{-17} $$ for some $c_3$ within an arbitrary subinterval of width $3 \times 10^6$ within the the interval $(10^6, 10^7).$
Now apply the same procedure once more to two subintervals of width $3 \times 10^6$ within the the interval $(10^6, 10^7),$ namely the intervals $(10^6, 4\times10^6)$ and $(7\times10^6, 10^7).$ This time the MVT gives us $$ \frac{-6.4 \times 10^{-17}}{d_2 - d_1} < f'''(d_3) < \frac{6.4 \times 10^{-17}}{d_2 - d_1} $$ for some $d_1 \in (10^6, 4\times10^6),$ $d_2 \in (7\times10^6, 10^7),$ and $d_3 \in (d_1, d_2).$ Then since $d_2 - d_1 > 3 \times 10^6$ and since $6.4 / 3 < 2.2,$ $$ -2.2 \times 10^{-23} < f^{(4)}(c_3) < 2.2 \times 10^{-23}. $$ But since $f(x)$ is a polynomial of degree $4$ or less, $f^{(4)}(x)$ is a constant.
This means that $f'''(x)$ can increase by at most $(6 \times 10^6)(2.2 \times 10^{-23}) = 1.32 \times 10^{-16}$ within the interval $(0, 6\times10^6).$ But $f'''(x_1) > -3.2 \times 10^{-17}$ for some $x_1 \in (3\times10^6, 6\times10^6),$ so $f'''(x)$ cannot be less than $-3.2 \times 10^{-17} - 1.32 \times 10^{-16} = -1.64 \times 10^{-16}$ anywhere in the interval $(0,x_1),$ and in particular in the subinterval $(0,3\times10^6).$
But now $f''(x)$ can decrease by at most $(3 \times 10^6)(1.64 \times 10^{-16}) = 4.92 \times 10^{-10}$ within the interval $(0, 3\times10^6).$ Since $f''(x_2) < 1.6 \times 10^{-11}$ for some $x_2 \in (1.5\times10^6, 3\times10^6),$ $f''(x)$ cannot exceed $1.6 \times 10^{-11} + 4.92 \times 10^{-10} = 5.08 \times 10^{-10}$ in the interval $(0,x_1),$ and in particular in the subinterval $(0,1.5\times10^6).$
This means $f'(x)$ can increase by at most $(1.5 \times 10^6)(5.08 \times 10^{-10}) = 0.000762$ within the interval $(0, 1.5\times10^6).$ Since $f'(x_3) \geq -0.0004$ for some $x_3 \in (10^6, 1.5\times10^6),$ $f'(x)$ cannot be less than $-0.0004 - 0.000762 = -0.001162$ in the interval $(0,x_3),$ and in particular in the subinterval $(0,10^6).$
This means that in the interval $(0,10^6),$ $f(x)$ cannot decrease by more than $10^6 \times -0.001162 = 1162.$ But since $f(10^6) = 100,$ it follows that $f(0) \leq 1262.$
In conclusion, there is no polynomial $f(x)$ of degree $4$ or less such that $\lvert f(x) \rvert \leq 100$ for $10^6 < x < 10^7$ and $f(0) = 10^6.$
You might want to reconsider whether the interpolating function has to be a polynomial.