There is a counterexample to Proposition 1 iff $\mathsf{P}\ne\mathsf{PSPACE}$. The idea is to make pair $f,g$ such that on certain inputs iterations of them individually is trivial, but by combination we perform computation of a deciding algorithm for some $\mathsf{PSPACE}$-complete problem.

If $\mathsf{P}=\mathsf{PSPACE}$, then since $f^n(g^m(x))$ could be computed in polynomial space from $x$, we would be able to compute $f^n(g^m(x))$ in polynomial time.

Further assume that $\mathsf{P}\ne \mathsf{PSPACE}$. Let $L\subseteq \{0,1\}^{\star}$ be some $\mathsf{PSPACE}$-compete problem. Let $T$ be a Turing machine and $P(x)$ be a polynomial such that $T$ checks if $\alpha\in L$ using at most  $P(|\alpha|)$ cells of the tape. For an appropriate polynomial $Q(x)$ that is strictly monotone as a function $\mathbb{N}\to\mathbb{N}$, we could  naturally code all possible states of $T$ for computations on inputs $\alpha\in \{0,1\}^n$ as strings of the length $Q(n)$. Let $h$ be a polynomial time function preserving the lengths of strings such that whenever it maps codes of states of $T$ as above to the codes of states of $T$ after one step of computation (and we don't care what happen with the strings that are not codes as long as we preserve their lengths). For $\alpha,\beta,\gamma\in\{0,1\}^{Q(n)}$ let $\alpha'=\min(\alpha+1,2^{Q(n)}-1)$ and $\beta'=\min(\beta+1,2^{Q(n)}-1)$, where we treat strings of the length $Q(n)$ as codes for numbers $<2^{Q(n)}$, we put
$$f(\alpha\beta\gamma)=\alpha'\beta h^{\min(\alpha',\beta)-\min(\alpha,\beta)}(\gamma)\text{ and }g(\alpha\beta\gamma)=\alpha\beta'h^{\min(\alpha,\beta')-\min(\alpha,\beta)}(\gamma).$$
Clearly, $$f(g(\alpha\beta\gamma))=g(f(\alpha\beta\gamma)=\alpha'\beta'h^{\min(\alpha',\beta')-\min(\alpha,\beta)}(\gamma).$$
We don't care about the behavior's of $f,g$ on inputs of other forms (as long as we have commutation and length preservation). Since $\min(\alpha',\beta)-\min(\alpha,\beta)$ and $\min(\alpha,\beta')-\min(\alpha,\beta)$ are always either $0$ or $1$, we could make $f$ and $g$ polynomial time computable.

Assume for a contradiction that there is a polynomial time algorithm prescribed by Proposition 1. Let $u$ be the polynomial time function mapping $\alpha\in\{0,1\}^n$ to $u(\alpha)\in\{0,1\}^{Q(n)}$ that codes the initial state of $T$ for the computation on the input $\alpha$. Now for appropriate polynomial time $n'(x)$ and $m'(x)$ we should be able to compute in polynomial time $f^{2^{Q(|\alpha|)}}(g^{2^{Q(|\alpha|)}}(00u(\alpha)))$ from $2^{Q(|\alpha|)}$, $f^{n'(2^{Q(|\alpha|)})}(00u(\alpha))$ and $g^{m'(2^{Q(|\alpha|)})}(00u(\alpha))$; here I am abusing the notation and by $00u(\alpha)$ I mean the string of the length $3Q(n)$ coding triple consisting of $0,0$, and $u(\alpha)$. Clearly, $$f^{2^{Q(|\alpha|)}}(g^{2^{Q(|\alpha|)}}(00u(\alpha)))=(2^{Q(|\alpha|)-1})(2^{Q(|\alpha|)-1})h^{2^{Q(|\alpha|)}-1}(u(\alpha)),$$ $$f^{n'(2^{Q(|\alpha|)})}(00u(\alpha))= (\min(2^{Q(|\alpha|)-1},n'(2^{Q(|\alpha|)}))(0)u(\alpha)\text{, and}$$
$$g^{m'(2^{Q(|\alpha|)})}(00u(\alpha))= (0)(\min(2^{Q(|\alpha|)-1},m'(2^{Q(|\alpha|)}))u(\alpha).$$
Hence we could compute $h^{2^{Q(|\alpha|)}-1}$ in polynomial time from $\alpha$. But since $T$ on the input $\alpha$ terminates after at most $2^{Q(|\alpha|)}-1$ steps (simply due to the number of possible distinct states), $h^{2^{Q(|\alpha|)}-1}$ will always be the code of the terminal state of the computation of $T$ on the input $\alpha$. Hence we would be able to decide the problem $L$ in polynomial time. Contradiction.