I think there's a very subtle difference that is almost intangible, but I'm trying to convey my thoughts anyway.
In short words: Willkür refers to a willful choice. The derived adjective willkürlich roughly corresponds to willful (in the sense of being headstrong — eigensinnig in German that is). And the yet derived substantive Willkürlichkeit expresses the presence of willfulness.
Willkür consists of Wille and Kür (cf. Canoonet). The word Kür express that you (can) act on your own decision. In sports competition, for example, there are figures or exercises that you must do (Pflicht) and some that you can add (Kür). There's the saying "Nach der Pflicht kommt die Kür". Also, the verb küren means wählen.
As such, you decide on your own what you do and, by that, you push through your will. Willkür.
You find more detailed information about it in Grimm.
So, a decision that only covers your will but doesn't consider other people involved is, thus, called a willkürliche Entscheidung (by turning it into an adjective), or you'd say "Die Entscheidung war reine/schiere Willkür".
It's commonly used with reference to politics and anything related to the state. Staatliche Willkür, politische Willkür, polizeiliche Willkür, Willkür von Behörden, Willkür des Königs. It's usually used in a negative sense, and words like Ungerechtigkeit are used in relation to it.
Anyway, for the comparison to Willkürlichkeit, what you need to remember is that Willkür addresses the decision of someone; or the fact that someone made a particular decision based on their will.
Willkürlichkeit, in contrast, refers to the presence of Willkür, or the fact that a person tends to exercise Willkür. Die Willkürlichkeit einiger Beamten, zur Willkürlichkeit neigen, Willkürlichkeit ist (nicht) auszuschließen are a few possible collocations. You can, though, often interchange the words without changing your statement.
This word is also defined in Grimm. You'll find a few further examples there.
Here's a made-up example using both words in contrast to each other.
Die Willkür seiner Entscheidung spiegelt die Willkürlichkeit so mancher machthabenden Personen dar.
Besides, Willkür is used in mathematics and natural science, and it is also a medical term.