There is no contradiction.
The threshold theorem requires that the error rate, i.e. error probability per gate (or per unit of time), be below a threshold. On the other hand, the exponential decay characterizes the absolute success probability, i.e. success probability in a computation involving a given number of gates (or of a given duration).
A little more formally, we can recognize the consistency between the two by estimating the absolute success probability $p$ of a computation consisting of $k$ gates under the assumption of constant per gate error probability $q$. A computation succeeds when every gate succeeds, so assuming errors are independent, we have$^1$
$$
p = (1-q)^k = e^{-\alpha k}\tag1
$$
where $\alpha=\ln\left(\frac{1}{1-q}\right)$. Thus, the assumption of constant per gate error probability makes the absolute success probability decay exponentially in the overall number of gates. Comparing to the equation in the question we see that, in this respect, decoherence behaves just like any source of error of constant per gate probability.
Now, the reason this exponential decay is not believed to stand in the way of practical large-scale quantum computers is that quantum error correction (QEC) provides the means of exponentially suppressing per (logical) gate error probability. In other words, QEC enables us to make $q$ as close to zero as we need for $p$ to be as close to $1$ as we desire. See this other answer of mine for a little more details.
$^1$ We're neglecting the highly remote possibility of multiple errors cancelling each other out.