Combining Steve's idea with the Beurling-Hormander uncertainty principle yields the kind of result you're looking for.
The BHUP is the following:
Beurling-Hormander Uncertainty Principle: If $f\in L^1(\mathbb{R})$ and $$ \int\int_{\mathbb{R}^2}|f(x)\hat f(y)|e^{|xy|}dxdy<\infty, $$ then $f=0$.
As a corollary, we have a Hardy uncertainty principle type result:
Corollary: If $\phi(x)$ and $\psi(y)$ are convex conjugates (so that
$\phi(x)+\psi(y)\geq xy$), and if
$$\int_{-\infty}^\infty|f(x)|e^{\phi(x)}dx<\infty\quad\mbox{and}\quad\int_{-\infty}^\infty |\hat f(y)|e^{\psi(y)}dy<\infty,$$ then $f=0$.
These theorems are stated for $\hat f(y)=\int_{-\infty}^\infty f(x)e^{-ixy}dx$.
Note that $\psi(y)$ is essentially the Legendre transform of $\phi(x)$:
$$\psi(y)=\sup_x xy-\phi(x).$$
Also, note that we can ignore a bounded part of the domain of $\hat f$, since $|\hat f(y)|\leq\Vert f\Vert_1$.
Now like Steve said, setting $f(x)=g(e^{-x})$, we have $\hat f(y)=Mg(iy)$.
Note that $f\in L^1(\mathbb{R},dx)$ if and only if $g\in L^1(\mathbb{R}_{>0},\frac{dx}x)$.
Thus the BHUP for Mellin Transforms is as follows:
BHUP for Mellin Transforms: Let $g$ be a function in
$L^1(\mathbb{R}_{>0},\frac{dx}x)$.
If $$ \int_0^\infty\int_{-\infty}^\infty |g(x)||Mg(iy)|e^{|\ln(x)\cdot y|}\frac{dx}{x}dy<\infty,$$ then $g=0$.
If $\phi(x)$ and $\psi(y)$ are functions such that $\phi(x)+\psi(y)\geq xy$, then the Hardy uncertainty principle type result translates to:
Corollary: If
$$\int_0^\infty |g(x)|e^{\phi(-\ln x)}\frac{dx}x<\infty\quad\mbox{and}\quad\int_{-\infty}^\infty |Mg(iy)|e^{\psi(y)}dy<\infty,$$
then $g=0$.
Now suppose that $g$ is a non-zero function in $L^1(\mathbb{R}_{>0},\frac{dx}x)$ such that $|g(t)|=O(e^{-t^r}/t^\delta)$ for some $\delta>0$.
If we choose $\phi(x)=e^{-rx}$, then
$$\int_0^\infty |g(x)|e^{\phi(-\ln x)}\frac{dx}x <\infty.$$
Thus $Mg(it)$ cannot decay (significantly) faster than $|t|^{-1}e^{-\psi(t)}$, where $\psi(t)$ is (something like) the Legendre transform of $e^{-rx}$.
What we need is $\psi(t)\geq |xt|-e^{-rx}$ for all $t$ outside some interval.
I think that taking
$$\psi(t)=\frac{|t|}r \ln\left(\frac{|t|}r\right)-\frac{|t|}r\qquad\mbox{for}\quad |t|>r$$
works.
Thus as $t\to\infty$, $|Mg(\pm it)|$ cannot decay faster than roughly $e^{-\frac tr\ln\frac tr}$.
This isn't quite as sharp as you were hoping for, but I probably haven't done the most careful analysis.