How can an accelerating inclined plane prevent a block on it from sliding? 
If I increase the force $F$, only the normal force $N1$ acting on $m1$ would increase which has no component along the plane, ie. along $m1gsin\theta$, so how would applying this force prevent m1 from sliding?
When I view it from the accelerated frame of the wedge,

It begins making sense. How is this possible? I'm really confused.
 A: 
Diagram 1 shows the arrangement with the inclined plane stationary.
There are two forces acting on the block, its weight $mg$ and the normal reaction on the block due to the inclined plane $N_1$.
The resultant of theses two forces is $F_1 ( = mg \sin \theta)$ and this force accelerates the block down the slope.
Diagram 2 shows the situation when a force $F$ is applied to the inclined plane and there is no relative movement between the block and the inclined plane.
That is because the resultant of the weight of the block $mg$ and the now increased normal reaction $N_2$ is a horizontal force $F_2$.
If that force $F_2$ on the block produces an acceleration of the block $a$ which is the same as the acceleration of the inclined plane then the block will not move relative to the inclined plane.
When this condition is satisfied $F_2 = ma$ and $F=(m+M)a$
Note that the magnitude of $F$ controls the magnitude of $N_2$ which in turn controls the direction of $F_2$.
If $F$ is larger than in the no relative movement condition then the magnitude of $N_2$ is larger and the block accelerates up the inclined plane whilst if $F$ is smaller then the block accelerates down the slope.
A: What causes the block to slide? That would be gravity.
What tries to prevent this slide? That would be friction.
And friction depends on the normal force $f_k=\mu_k n$.
As you rightfully say, the normal force increases with increasing pushing force $F$, which thus causes increased friction which thus prevents the slide.

Is the surface frictionless, then consider the same case purely from an acceleration component point of view:
With gravity alone, some normal force is present. It balances the perpendicular gravity component, so there is no acceleration in this direction. Only in the sliding direction is the gravity component not balanced. 
Now with the push, the normal force increases, so it is far larger than necessary to balance the perpendicular gravity component. So in the perpendicular direction there is now acceleration away from the surface.
But remember that the parallel gravity component is still there and still unbalanced.
Put this parallel and perpendicular component together and the resulting acceleration is straight ahead (in the pushing direction). 
In other words, the moving incline is pushing the block forward and upwards, while gravity is pulling it forward and downwards. So certainly, this upwards and downwards tendency can balance and only straight forward acceleration remains 
