...without using logarithms / exponentials ?
The approximation symbol in the title has been used loosely. But from now on I will be more precise.
Two of the key properties of logarithms are given by the identities:
$$ \ln a^b = b\ln a\qquad \forall a,b \geq 1 \quad(1),$$
$$ \ln a + \ln b = \ln ab \qquad \forall a,b \geq 1 \qquad (2). $$
It is also true that
$$ 0 < \sum_{k=1}^{n} \frac{1}{k} - \ln n \leq 1\qquad \forall n\geq 1\qquad (3).$$
Therefore,
$$ (1)\ \text{ and } (3)\ \implies \left\vert \sum_{k=1}^{\large{n^m}} \frac{1}{k} - m \sum_{k=1}^{\large{n}} \frac{1}{k} \right\vert \leq m \qquad \forall n,m \geq 1 \qquad (4),$$
and
$$(2)\ \text{ and } (3)\ \implies \left\vert \sum_{k=1}^{\large{i}} \frac{1}{k} + \sum_{k=1}^{\large{j}} \frac{1}{k} - \sum_{k=1}^{\large{ij}} \frac{1}{k} \right\vert \leq 2 \qquad \forall i,j \geq 1. \qquad (5). $$
So the following natural question arises:
Can we prove inequalities $(4)$ and $(5)$ without reference to $\ln$ or $\exp$?
$(4)$ is easy to prove for all $m$ given $n=1$, and all $n$ given $m=1.$ And but I don't know where to start for $n,m \geq 2.$
Similarly, $(5)$ is easy to prove for all $j$ given $i=1$, and all $i$ given $j=1.$ And but I don't know where to start for $i,j \geq 2.$
I don't think induction without any other tools gets us far.
It will be more convenient in what follows to think of $H_{n-1}$ as the function which approximates $\log n$ (after all it's the left Riemann sum). The basic idea is to prove that
$$H_{nm-1} - H_{n-1} = \sum_{i=n}^{nm - 1} \frac{1}{i} \approx H_{m-1}$$
which we can do by breaking the sum up into arithmetic progressions: it's equal to
$$\sum_{j=0}^{n-1} \sum_{k=1}^{m-1} \frac{1}{nk + j}$$
which if we eyeball it is roughly $n \sum_{k=1}^{m-1} \frac{1}{nk} = H_{m-1}$. The difference between the two is bounded by
$$\begin{align*} \sum_{j=0}^{n-1} \sum_{k=1}^{m-1} \left( \frac{1}{nk} - \frac{1}{nk + j} \right) &= \sum_{j=1}^{n-1} \sum_{k=1}^{m-1} \frac{j}{nk(nk+j)} \\ & \le \sum_{j=1}^{n-1} \sum_{k=1}^{m-1} \frac{j}{n^2 k^2} \\ & = \frac{1}{n^2} \sum_{j=1}^{n-1} j \sum_{k=1}^{m-1} \frac{1}{k^2} \\ & \le \frac{1}{n^2} {n \choose 2} \sum_{k=1}^{\infty} \frac{1}{k^2} \\ & \le \frac{\pi^2}{12} \approx 0.822 \dots \end{align*}$$
which altogether gives
$$\boxed{ |H_{nm-1} - H_{n-1} - H_{m-1}| \le \frac{\pi^2}{12} }$$
Applying this bound $m-1$ times gives
$$\boxed{ |H_{n^m - 1} - m H_{n-1}| \le \frac{\pi^2}{12} (m-1) }.$$
and both of these can probably be tightened. This argument is the discrete analogue of the continuous argument where we show that
$$\int_a^{ab} \frac{dx}{x} = \int_1^b \frac{dx}{x}$$
using the $u$-substitution $u = \frac{x}{a}$. Here in the discrete setting we don't have the perfect scaling symmetry that sends the interval $[1, b]$ to the interval $[a, ab]$ but we do have it approximately and that's what we use.