You have asked a good question.
…it does not seem to me that the projectile is simple parabola (as in the ground case) that can be "cut" into halves. So, why does this work?
Really it contrasts with the symmetry. But it has nothing to do with symmetry. You will better understand with following graphs.
Here black line indicates the trajectory of the ball and brown line is the inclined plane.
As @John Rennie precisely explained,
....the word "peak" means maximum distance from the plane measured normal to the plane. It does not mean the maximum height measured from the horizontal.
I have marked them as 'A' and 'B' respectively.
If you try graphing this yourself you will realize that distances $a$ and $b$ in the following picture are equal (This property was discovered by Archimedes).*
Since there is no horizontal acceleration, the amounts of time that the ball takes to pass $a$ and $b$ are equal (consider horizontal motion). Eventually you will conclude that that the time of the flight is given by doubling the time to reach the peak(A).
Thus it is not due to symmetry, but because of the special property of intersection of a straight line and a parabola.
Hope this helps.
P.S.: @Fredriksy has also explained the same thing in his answer,
It seems like you are worried that the flight path after you rotate the picture (x-y axes) is NOT a parabola. However this is not actually important for determining the time of flight.
I guess, with this explanation and my graphs you will understand better. Good luck.
*You can find the mathematical proof here.
(Special thanks go to @CiaPan and @Pope)
EDIT:
Can you observe something else interesting? If you consider a projection relative to the horizontal plane, the horizontal plane will also be a chord to the trajectory, which is a parabola. So the observation, 'by doubling the time it takes to reach maximum altitude with respect to the considered plane, flight time is obtained ', can also be interpreted as a result of this special property of intersection, although it obviously seems to be a consequence due to symmetry:-)
Best Answer
On an intuitive level, the initial speed $v_0$ can be considered to have two effects: one on the horizontal velocity, and one on the vertical; the former affects the range in a direct sense, and the latter increases the time the projectile is in the air. The combination of both of these gives an overall $v_0^2$ contribution.
If you were to increase the horizontal velocity on its own (not touching the vertical), you would proportionally increase the range. Similarly if you increased the vertical velocity you would increase the range. Increasing both of these, which is what increasing $v_0$ does, will increase the range twice, but multiplicatively. Think of it like a square - if you increase both sides by the same amount (e.g. 3 times), you increase the area by that amount squared (9 times).