The short answer is: They prepend bits in that way because the scheme is not secure without them. While they might not explain it in English, their proof makes it clear where they use it.
Let us construct an attack against the scheme that does not prepend a bit to the blocks. The same idea will work against a version of the scheme that prepends the same bit to every block. In this version of the scheme, a tag for a single-block message $M\in\{0,1\}^{32}$ is $(r,z)$, where $$z = F_a(r)\oplus F_a(\langle1\rangle\| M).$$
Our attack will obtain about $2^{32}$ tags for an arbitrary single-block message $M$, stopping
if it ever gets a tag $(r,z)$ such that the upper $32$ bits of $r$ are equal to
$\langle1\rangle\in\{0,1\}^{32}$ and lower $32$ bits are not equal to $M$. When it finds such a tag $(r,z)$, let $s\neq M$ denote
the lower $32$ bits of that $r$. The adversary outputs a forgery on the message $M' = s$ with tag $(r',z')$ defined by
$$r' = \langle 1\rangle\| M \quad \text{ and } \quad z' =z$$ This tag will verify with message $M'$ because
$$z' = z= F_a(r)\oplus F_a(\langle 1 \rangle\|M)= F_a(r')\oplus F_z(\langle 1 \rangle\| M'),$$
where the second equality uses the fact that our $r$ is equal to $\langle 1\rangle\| s = \langle 1\rangle\| M'$ (it switches the order of the arguments to $\oplus$). Moreover, our adversary never queries the message $M'$ and one can verify that it will get the needed $r$ with good probability in about $2^{32}$ tries, so it will win the security game.
The intuition is that prepending the bits prevents this sort of thing from happening. Specifically, this adversary found a way to force the verification algorithm to treat a previously used $r$ as a message, which can't happen with their domain separation strategy.
