I claim that $M_r = 2r+1$ does the trick.
Denote $T=(t_0,\dots,t_p)$, $U=(u_0,\dots,u_p)$, $\|U\|= \sum_{j=1}^p|u_{j-1}-u_j|$ and $G(U) = \sum_{j=0}^p|g(t_j,u_j)|$. We have to prove that $G(U) \le 2\|U\|+1$ for all possible $U$. Here is a visualization (the values in the middle are the non-zero values of $g$):
If we stay in one layer over a period $\Delta t$, then $G(U)$ increases at most by $\Delta t$. Therefore, staying in one layer for the whole time yields $G(U)\le 1$ and $\|U\|=0$.
If we switch into some layer $k$ (over a time period $\Delta t$), we gain (compared to staying in the previous layer) at most $\Delta G = \frac{1}{2^k}$, which is the value of $g$ in the $k$-th layer, while paying the prize of at least $\Delta\|U\| = \frac{1}{2^{k-1}}$, which is the minimal distance from layer $k$ to another layer.
Therefore the ratio is at most $2$, since
$$
\frac{\Delta G }{\Delta\|U\|} \le 2
$$
These considerations imply $G(U) \le 1 + 2\|U\|$ for all possible $U$.
Remark: $M_r = 2r+1$ is probably not a tight bound.
Call $\| f\|_{BV}$ the supremum in definition 1.
Notice that if $f$ is smooth, then
$$
\int_{\mathbb{R}} f(x) \phi'(x) \, dx = - \int_\mathbb{R} f'(x)\phi(x)\, dx,
$$
and so by the duality between $L^1$ and $L^\infty$, we have $\| f\|_{BV}= \| f'\|_1$ (you can absorb the minus sign into $\phi$).
Now, under the same assumption that $f$ is smooth, by the fundamental theorem of calculus,
$$
\int_\mathbb{R}|f(x+h)-f(x)|\, dx = \int_\mathbb{R} \left| \int_0^1 f'(x+th)h\, dt\right| \, dx \leq \int_0^1\int_\mathbb{R} |f'(x+th)|\, dx |h|\, dt = \| f'\|_{1}|h|.
$$
This is the inequality in this case. To pass to general $f$ we mollify.
Consider a function $\eta\in C_c^\infty(\mathbb{R})$ supported on the unit ball, nonnegative, even, and $\int_{\mathbb{R}}\eta(x)\, dx =1$. For $\varepsilon>0$ define $\eta_{\varepsilon}(x)=\varepsilon^{-1}\eta(x/\varepsilon)$ and set $g_\varepsilon= g*\eta_\varepsilon$ for any $g\in L^1_{loc}$, i.e.
$$
g_\varepsilon(x):= \int_{\mathbb{R}} g(y)\eta_{\varepsilon}(x-y)\, dy.
$$
Now fix $\phi\in C_c^\infty(\mathbb{R})$ with $\| \phi\|_\infty\leq 1$, then by Fubini's theorem and using that $\eta_\varepsilon$ is even we have
$$
\int_\mathbb{R} f_\varepsilon(x)\phi'(x)\,dx = \int_\mathbb{R}f(x) (\phi')_\varepsilon(x)\, dx = \int_\mathbb{R} f(x) \phi_\varepsilon'(x)\, dx,
$$
where the last equality is due to the fact that convolution commutes with derivatives. Since $\| \phi_\varepsilon\|_\infty\leq \| \phi\|_\infty\leq 1$, we see that $\| f_\varepsilon\|_{BV}\leq \| f\|_{BV}$. We're now ready to finish: Fix $f\in L^1(\mathbb{R})$ with $\| f\|_{BV}<\infty$ and consider the $f_\varepsilon$ as above, then
$$
\int_{\mathbb{R}}|f_\varepsilon(x+h)-f_\varepsilon(x)|\, dx \leq \| f_\varepsilon\|_{BV}|h| \leq \| f\|_{BV} |h|,
$$
and now simply let $\varepsilon\to 0^+$, using that $f_\varepsilon\to f$ in $L^1$ to conclude.
Added: I should also note that (under the $f\in L^1(\mathbb{R})$ background assumption) the two definition are equivalent, if we pick the right representatives (which is obviously necessary, since elements in Def 1 are equivalence classes, while in Def 2 we talk about pointwise values). This is done in G. Leoni's book "A first course in Sobolev spaces". In your example, the Dirichlet function is a.e. equal to a constant, which is clearly of bounded variation no matter the definition.
Best Answer
By definition, $f_n$ can be periodically extended to the whole $\mathbb R$, and then $f$ is a continuous function defined on $\mathbb R$ with period $1$. This extension is merely for simplicity of the proof below. We claim that
From the above claim, we know that $f$ is of unbounded variation on any closed interval, since a continuous function of bounded variation is differentiable almost everywhere, see the last line of the introduction part of this wikipieda page.
We prove the claim using the following lemma.
It is not hard to prove this lemma, so we left the proof to reader.
Now we show that $f$ defined in OP is not differentiable at any point. Let $x_0$ be any real number. We assume that $f$ is differentiable at $x_0$ and we look for a contradiction. For each $n\in\mathbb N_{\geq1}$, there exists a unique $m_n\in\mathbb Z$ such that $\frac{m_n}{2^n}\leq x_0< \frac{m_n+1}{2^n}$. We take $u_n=\frac{m_n}{2^n}, v_n=\frac{m_n+1}{2^n}$, then $u_n\leq x_0< v_n$, $\{u_n\}$ is non-decreasing, $\{v_n\}$ is non-increasing, and $\lim_{n\to\infty}(v_n-u_n)=0$. By definition, $u_n$ and $v_n$ lie in the same segment of $f_n$, so they lie in the same segment of $f_k$ for all $k\leq n$. Hence, for $1\leq k\leq n$ we have $f_k(v_n)-f_k(u_n)=\pm 2^{k+1}(v_n-u_n)$. For $k\geq n+1$, we have $f_k(u_n)=(-1)^{2^{k-n}m_n}=1=(-1)^{2^{k-n}(m_n+1)}=f_k(v_n)$. Therefore, $$\frac12\frac{f(v_n)-f(u_n)}{v_n-u_n}=\frac12 \sum_{k=1}^n\frac1{2^k}\frac{f_k(v_n)-f_k(u_n)}{v_n-u_n}=\sum_{k=1}^n(\pm1).$$ As a result, if $n$ is odd, then $\frac12\frac{f(v_n)-f(u_n)}{v_n-u_n}$ is odd; if $n$ is even, then $\frac12\frac{f(v_n)-f(u_n)}{v_n-u_n}$ is even. Thus the limit $$\lim_{n\to\infty}\frac12\frac{f(v_n)-f(u_n)}{v_n-u_n}$$ does not exist. This contradicts to our assumption of the differentiability of $f$ at $x_0$.