The exponential distribution is the $\mathbf{\underline{only}}$ distribution that has the memoryless property. See this MathSE post.
Now that doesn't necessarily imply a Markov process must have only exponential jump times, but any examples without exponential jump times will likely be fairly trivial. The requirement is that the distribution of the future states of the process only depend on the most recent state known and not any other information about the past.
To answer your question: "how does having a non-exponential distribution give the process memory?" It is simply because The distribution of the process at a future time will depend on more than just the most recently known state. Memorylessness means not that we don't know the past, but that we don't need to know it (except for the most recent memory). I.e. that $P(X_t\in A \mid X_s \text{ for } s\leq s_0<t)=P(X_t\in A \mid X_{s_0})$.
With a uniform wait time, there is a maximum amount of time that will be spent in that state. Without knowing when the state was entered, there is no way to calculate probabilities on when it will leave the state.
Even if we choose some other nonuniform random distirbution that has support on $[0,\infty)$ that isn't exponential, it still won't have the memoryless property though, since as discussed above, the exponential is the only distribution with this property.
See this MathSE post for a process with uniform jump times and is not Markov.
Here is a MathSE post that is relevant. Here is the important paragraph:
In order for a process to have non-exponential wait times and satisfy
the Markov property, knowing the current state must give away the
precise time that it entered that state. Consider the process that
starts in one state, stays there for some random length of time, then
jumps to another state and stays there forever. It's Markov, but not
very interesting. Knowing the current state means you know whether or
not the jump has occurred and can calculate the distribution of future
states precisely.
Example of a process with a uniform jump time that is Markov:
Consider the process that starts in state $0$ and jumps to state $1$ after a uniform time in $[0,1]$. Let's assume that we know $X_s$ for all $s\leq s_0$. We want to show that
$$P(X_t\in A\mid X_s \text{ for } s\leq s_0<t)=P(X_t \in A\mid X_{s_0})$$
so that this process does indeed have the Markov property.
Let $t<1$. If $A=\{0\}$, then $P(X_t=0\mid X_s \text{ for } s\leq s_0<t)$ equals $0$ if $X_s$ is $1$ (the jump has already occurred) for any $s\leq s_0$ (i.e. if $X_{s_0}=1$, so we only need to know $X_{s_0}$). Furthermore, $P(X_t=0\mid X_s \text{ for } s\leq s_0<t)$ equals $P(u> t \mid u>s_0)=P(X_t=0 \mid X_{s_0}=0)$. So we conclude that
$$P(X_t=0\mid X_s \text{ for } s\leq s_0<t)=P(X_t=0 \mid X_{s_0})$$
Similarly, if $A=\{1\}$, then $P(X_t=1\mid X_s \text{ for } s\leq s_0<t)$ equals $1$ if the jump has already occurred, that is if $X_{s_0}=1$. And it equals $P(u\leq t \mid u>s_0)=P(X_t=1 \mid X_{s_0}=0)$ if the jump has not occurred yet during the know interval $[0,s_0]$.
Let $t\geq 1$. Then $P(X_t=0\mid X_s \text{ for } s\leq s_0<t)=P(X_t=0\mid X_{s_0})=P(X_t=0)=0$ and $P(X_t=1\mid X_s \text{ for } s\leq s_0<t)=P(X_t=1\mid X_{s_0})=P(X_t=1)=1$.
Thus
$$P(X_t \in A\mid X_s \text{ for } s\leq s_0<t)=P(X_t \in A \mid X_{s_0}).$$
So this is indeed a Markov process where the wait time is not exponentially distributed.
For an even more trivial example, consider the process $X_t=1$ for all $t\in[0,\infty)$. Trivially,
$$P(X_t\in A \mid X_s, s\leq s_0)=\begin{cases}
0 &\text{ if } 1\notin A\\
1 &\text{ if } 1\in A
\end{cases}
$$
and
$$P(X_t\in A \mid X_{s_0})=\begin{cases}
0 &\text{ if } 1\notin A\\
1 &\text{ if } 1\in A
\end{cases}
$$
showing that it is indeed a (trivial) Markov process.