Why is capacitor a linear element?

First of all, an I-V curve does not make any sense for a capacitor. This is because a capacitor follows the following equation: $$i = C \frac{dV}{dt}$$

Note that the current depends on the rate of change of voltage. So you can have the same current at two different voltages, if the rate of change is the same.

The reason a capacitor is a linear device is because differentiation is linear. Superposition becomes: $$i_1 +i_2 = \frac{d}{dt}(v_1 + v_2) = \frac{dv_1}{dt} + \frac{dv_2}{dt}$$

Your assumption is wrong:

It has non linear I-V characteristics

An ideal capacitor, just like an ideal resistor, has linear I/V characteristics.

Since you're obviously learning linear circuit analysis (judging by your knowledge of the superposition principle), I'm absolutely certain you've learned (or will very soon learn, by reading your course's material) about representing harmonic currents by complex currents.

With complex currents and voltage representations, it's really easy to see that a capacitor is a linear device.

\begin{align} I(t) &= C\frac {dU(t)}{dt} & \text{the elementary capacitor formula}\\ &\text{hinting at linearity}\\ I_\text{sum}(t) &= C\frac{dU_\text{sum}}{dt}&U_\text{sum} = U_1+U_2\\ &\overset!= C\frac {dU_1(t)}{dt}+C\frac {dU_1(t)}{dt}\\ \end{align} which is the case because the differentiation \$\frac d{dt}\$ is linear.

You might really just be confused by "linear" as term.

The formal definition of a "linear" function, as in linear system, is that if you scale the input of the function by some amount, the output is scaled by that same amount:

  y = f(x)
  f(Ax) = Ay

Note that F() adding a offset inside violates this.

As you said, one way to describe a capacitor is V = Q / C. This says that the voltage on a capacitor is proportional to the charge it is holding, and that proportionality constant is the inverse of the capacitance. In the parlance of a linear equation as above, V = f(Q). Since f(Q) = Q/C, it should be clear that this equation is linear because:

  A * Q / C = A * V

for arbitrary values of A.