I know it is covalent because there are covalent bonds between atoms of carbon in the same plane. But there are Van der Waals interactions between different planes. Isn't this a feature of molecular solids?
Graphite is odd in its categorisation and does by no means rigorously follow the conventions of either a covalent solid, or a molecular solid (for example it can conduct electricity). Graphite has properties of both molecular solids (it is soft), and covalent solids (it has a very high melting point. In fact it will break down before it melts.).
For this reason, the categorisation of some materials, such as graphite, can be somewhat complicated, and the idea of graphite being a covalent solid really just comes from its similarity with other covalent solids.