To supplement the answer by Luboš Motl, I will come to this problem from a Material Science point of view.
What you mean by the inherent property of the string is not the spring constant, in fact, it is Young's modulus $E$, which is defined to be the same for some material (and not only for a string):
$$
E = \frac{\text{tensile stress}}{\text{tensile strain}}
= \frac{\sigma}{\varepsilon}
= \frac{\text{force per area}}{\text{extension per length}}
= \frac{F / A}{x / l}
= \frac{F l }{x A}
$$
Now use this definition to construct the Hooke's Law:
$$
F = \frac{EA}{l} x = k x
$$
where
$$
k = \frac{EA}{l}
$$
Now if you think, when cutting a string in half, you are keeping $E$ and $A$ constant (the same material and the same cross-sectional area), but you change $l$ by a factor of $4$. This makes the new $k$ to be 4 times smaller.
Also, $E$ is not always constant for some type of material, but greatly depends on the micro-structure of it, such as tiny imperfections in the crystalline structure, which influence $E$ in different ways.
Note, that a rigorous proof, would involve the geometry of the spring as well, but it would only influence the effective size of the $EA$ product - the scaling with length would remain the same.
Some rambling on $E$
I thought I might talk about why $E$ is always constant for some type of material. We can imagine a slab to be constructed by lots of tiny springs, which obey the Hooke's law. (This is possible because of one approximation, that the atoms in the material do not move far from their equilibrium position.)
Because of the energy conservation we already know (the answer by Luboš Motl), that if we connect several springs, then we will change the effective spring constant:
$$
k_{new} = n * k
$$
where n is the number of the springs.
This means, that the percentage part of the extension is more sensible to measure, i.e.:
$$
F = const * x / l = const * \varepsilon
$$
using the previous definition.
The same if we connect several springs in parallel, the effective $k$ will scale with the number of springs we connect and the number of the strings will be proportional to the cross sectional area of the spring.
$$
F = const*A*x
$$
Where we can denote the unknown constant as the Young's modulus.