But as far as I know entropy is the amount of disorder.
Entropy is a measure of the number of possible microscopic states consistent with an observed macroscopic state1, $S = k_text{B}ln N$. Fundamentally it has nothing to do with disorder, although as an analogy it sometimes works. For example, in simple situations like an $n$ point-particle gas in a box: there many more ways to put point-particles in a box in disorderly manner than an orderly one. However, the exact the opposite may be true if they have a positive size and the box is crowded enough. Overall, disorder is just a bad analogy.
1 Even that's not quite true, but it's better than disorder. Specifically, it's a simplification under the assumption that all microstates are equally likely.
A black hole is denser than a star. For a density that high, I assume a certain amount of order (inverse entropy?) is required.
If an object is crushed inside ideal box that isolates it and prevents any leaks to the outside, the crushed object still has information about what it was before. And an event horizon is about as an ideal box as there can be.
Classically, black holes have no hair, meaning that the spacetime of an isolated black hole is characterized by mass, angular momentum, and electric charge. So there are two possible responses to this: either the black hole really has no structure other than those few parameters, in which case the information is destroyed, or it does have structure that's just not externally observable classically.
Thus, if information is not destroyed, we should expect the number of microstates of a black hole to be huge simply because there's a huge number of ways to produce a black hole. Roughly, at least the number of microstates of possible collapsing star remnants of the same mass, angular momentum, and charge (though this is idealized because a realistic collapsing process sheds a lot).
For a density that high, I assume a certain amount of order (inverse entropy?) is required.
Quite the opposite; black hole are the most entropic objects for their size.
In the early 1970s, physicists have noticed an interesting analogies between how black holes behave and the laws of thermodynamics. Most relevantly here, the surface gravity $kappa$ of a black hole is constant (paralleling zeroth law of thermodynamics) and the area $A$ of a black hole is classically nondecreasing (paralleling second law). This is extended further with analogies of the first and third laws of thermodynamics with $kappa$ acting like temperature and $A$ as the entropy.
The problem is that for this to be more than an analogy, black holes should radiate with temperature that's (some multiple of) their surface gravity. But they do; this is called Hawking radiation. So the area can shrink as long as there is a compensating entropy emitted to the outside:
$$deltaleft(S_text{outside} + Afrac{k_text{B}c^3}{4hbar G}right)geq 0text{.}$$
Thus, semi-classically, the entropy of a black hole is proportional to its surface area. In natural units, it is simply $S_text{BH} = A/4$, which is huge because Planck areas are very small.
Thus, we know that in a semi-classical approximation, a black hole must radiate with temperature proportional to its surface gravity and entropy proportional to its area. It's natural to wonder the next step: if a black hole has all this entropy, where is the structure? How can it have so many possible microstates if it's classically just a vacuum? But going there takes us to the land of quantum gravity, which is not yet firmly established, and is outside the scope for astronomy.