A Wilcoxon-Mann-Whitney is entirely suitable for testing equality of the parameter of (one-parameter) exponential distributions.
[While a Wilcoxon-Mann-Whitney is not in general a test of equality of medians, it will also be a test of equality of medians if you assume the two populations have the same distribution up to a change of scale - as would be the case with the exponential.]
For example, under the null (implying iid exponential variates), the significance level will have exactly the properties as should be expected with a Wilcoxon-Mann-Whitney test at whichever sample sizes you have (naturally not all significance levels will be available with a non-randomized test but it will be the same issue as it would be in the situations you're more used to).
Power will be reasonable*, but obviously at any exact distributional model, below the power of the most powerful test for that distribution. [You can get a uniformly most powerful one-tailed test via the Karlin-Rubin theorem, which would boil down to a one-tailed F test based on a ratio of the sample means. An equal-area two-tailed F test will not be UMP but will perform very well in large samples.]
You correctly note that the alternative in the case of an exponential is not a shift alternative but that is not of any particular consequence, other than if you try to use the test to produce a confidence interval for a location shift, it won't be useful when you're not dealing with a location shift.
You can instead readily produce an interval for the scale shift by the usual strategy of inverting the test; it's the set of values for the scale shift that don't lead to rejection.
However, there's a neat shortcut if you have software that will give an interval for a shift, which is to simply take logs, get the interval for the shift on the log scale and exponentiate its endpoints; that should be identical to the exact interval by inverting the scale shift on the original data.
* Indeed, a quick simulation at a few sample sizes suggests that the one-tailed Wilcoxon-Mann-Whitney has fairly reasonable small sample power compared to the likelihood ratio test conducted at the same significance level as that of the WMW, for exponential populations. (Not as good relative efficiency as you get with the normal, but it looks reasonable.)
It actually looks to me like you have heavier right tails than the exponential would suggest; it may be that the WMW has better power in that situation than using a UMP test for the exponential when actually sampling some more-skew populations.