The relationship between kinetic energy (K.E) and momentum (p) of a body can be expressed through their respective definitions. Kinetic energy is given by $$K.E = \frac{1}{2} mv^2$$ where $m$ is the mass of the body and $v$ is its velocity. The momentum (p) of a body is given by $$p = mv$$. To express kinetic energy in terms of momentum, we can manipulate the expression for momentum as follows:

$$p = mv \implies v = \frac{p}{m}$$

Substituting $v$ in the kinetic energy formula, we get

$$K.E = \frac{1}{2} m\left(\frac{p}{m}\right)^2 = \frac{1}{2} \frac{p^2}{m}$$

Therefore, we see that kinetic energy is directly proportional to the square of the momentum $(K.E \propto p^2)$.

Now, given that the kinetic energy of a body becomes 36 times its original value, we can set up the proportionality as

$$\frac{K.E_{\text{final}}}{K.E_{\text{original}}} = 36$$

Since $K.E_{\text{final}} = 36 \times K.E_{\text{original}}$ and knowing $K.E \propto p^2$, we can express this relationship through the squares of the initial and final momentum:

$$\frac{p_{\text{final}}^2}{p_{\text{original}}^2} = 36$$

Taking the square root of both sides to find the ratio of final to initial momentum, we have

$$\frac{p_{\text{final}}}{p_{\text{original}}} = \sqrt{36} = 6$$

This indicates that the final momentum is 6 times the original momentum. To find the percentage increase in the momentum, we calculate the increase from the original to the final, subtracting the original momentum (which is considered 1 times itself):

$$\text{Percentage increase} = \left(\frac{p_{\text{final}} - p_{\text{original}}}{p_{\text{original}}}\right) \times 100\% = \left(\frac{6p - p}{p}\right) \times 100\% = \left(6 - 1\right) \times 100\% = 5 \times 100\% = 500\%$$

Therefore, the correct answer is Option B: 500%.