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.

Asymptotic expansions of integralsby Bleistein and Handelsman, especially Chapter 4. $\endgroup$ – Liviu Nicolaescu Jul 31 '13 at 17:15