Encoding an element in $r=r'||h(r')$ way
Question1: How can we show/prove that the random element only with a negligible probability can have such structure?


If we assume the random oracle model and have $h: \{0,1\}^* \to \{0,1\}^n$ then we can state that $h(.)$ is equivalent to randomly sampling from $\{0,1\}^n$. Thus for a random element $r = r'||r''$ the probability that $r$ has the structure $r'' = h(r')$ is $\frac{1}{2^n}$ since all $2^n$ possible outputs of $h(r')$ are equally likely. Thus for $n=160$ we have a probability of $\frac{1}{2^{160}}$ which is negligible.


  Question2: Can we reduce the $h(.)$ output size to 80-bit (which is not the standard hash function output size) and set $p$ as smaller prime number (e.g. 128-bit )and prove a random value can have the above structure with only negligible probability?


Sure, the same logic as above can be applied here as well, now with the case $n=80$ and a corresponding probability of $\frac{1}{2^{80}}$ which is still negligible. 

Note that the size of $r'$ is not relevant to the probability of a random element having the structure $r'||h(r')$, the probability solely depends on the size of $h(r')$.