How is normal force generated on wedge? suppose we have a wedge a block kept over it as shown and consider all surfaces to be smooth:

Now block $M$ and $m$ will exert normal ($N$) on each other with same magnitude.
As only force exerted by $m$ on $M$ is $mg\cos\theta$, we take $N$ exerted by $m$ on $M$ be $mg\cos\theta$, if so then, as force is exerted upon $M$, it will start moving towards left because of horizontal component of $N$, but how can then $mg$ possess it's effect in direction perpendicular to it?
If this not the cases then it's sure that horizontal velocity of $M$ will be because of $N$, which should imply that $N\neq mg\cos\theta$, so what should $N$ equals to? If only force on $M$ by $m$ is $mg\cos\theta$, what I'm missing?
 A: The Short Answer
Forget the quantitative analysis of forces that you have done. (There are some errors in it. To name a major one, the normal reaction force between the blocks won't be $mg\cos\theta$.) Let's qualitatively answer the following two questions: 

Will the wedge accelerate horizontally or not?

It will. 
Reason: We will analyze everything in the ground frame. Let's assume the wedge isn't accelerated horizontally. You can easily see that the block on the wedge will certainly move downwards along the surface of the wedge with some acceleration. Since the surface of the wedge is inclined to the horizontal at an angle other than $\dfrac{\pi}2$, there is a non-zero component of the acceleration of the block in the horizontal direction. If so, then the acceleration of the center of mass of the system is non-zero in the horizontal direction. This must not happen because the net force on the system is purely along the vertical direction. Thus, our initial assumption that the wedge doesn't accelerate horizontally is wrong. Rather it moves in the horizontal direction with some acceleration in order to cancel the effect of the block's acceleration in the horizontal direction - making the net acceleration of the center of mass zero in the horizontal direction. 

How can gravity - a downward force - can cause some acceleration in the horizontal direction?

This is a nice question. But as you can see, there is no net acceleration of the center of mass of the system in the horizontal direction. This is precisely the statement which forced us to conclude that the wedge must move horizontally with a non-zero acceleration. The horizontal acceleration of the wedge and the horizontal acceleration of the block add up to make the net horizontal acceleration of the center of mass zero. The reason the individual parts get some horizontal acceleration is owing to the fact that there are internal normal reaction forces in the system that have a non-zero horizontal component. These internal forces make system's parts acquire some horizontal acceleration. But they can't provide any horizontal acceleration to the center of mass. 
The Calculative Answer
Let's assume the normal reaction force between the wedge and the block to be $N$. Let's assume the horizontal acceleration of the wedge with respect to the ground to be $a$ towards the left. If the wedge is not going to accelerate then we will get $a=0$ - don't worry! Now, let's jump to the frame of reference attached with the wedge. Notice that this frame will see a pseudo force on both the wedge and the block corresponding to its acceleration $a$. 
Equations for the wedge
With respect to the wedge, the wedge is in equilibrium. Therefore,
$$N\sin\theta=Ma\tag{1}$$
We will ignore the equation of motion of the wedge in the vertical direction. It will be useful only to find the normal reaction force between the ground and the wedge which is not useful for the analysis of the motion of the wedge and block. 
Equations for the block
With respect to the wedge, the block moves along the surface of the wedge and wedge itself is at rest in equilibrium. Therefore, the equation of motions are simply: 
$$mg\sin\theta+ma\cos\theta=mb \tag{2}$$
$$mg\cos\theta-ma\sin\theta=N \tag{3}$$
Where $b$ is the acceleration of the block along the wedge surface as observed by the wedge. 
Solving these equations, we get $$a=\dfrac{g\sin2\theta}{2\bigg(\dfrac{M}{m}+\sin^2\theta\bigg)}\tag{4}$$ $$b=g\sin\theta\bigg(\dfrac{M+m}{M+m\sin^2\theta}\bigg)\tag{5}$$ $$N=\dfrac{g\cos\theta}{\bigg(\dfrac{1}{m}+\dfrac{\sin^2\theta}{M}\bigg)}\tag{6}$$
As you can see, your result $N=mg\cos\theta$ would have been valid if the wedge couldn't move, i.e. if $M\to\infty$
A: The only external forces on the system (Wedge + Block) is $R + mg + Mg$, where $R$ is normal reaction from the ground to the wedge. These three forces are all vertical in direction. Now, although it may seem that system should be moving only vertically because of vertical external forces, it's not correct because internal forces like $N$ in your case DOES play a role in determining the motion of individual bodies because $N$ is internal only for the system Wedge + block but it is external for the wedge and block individually. Newton's 2nd law applied on a multi-body system tells only about the acceleration of center of mass not about the internal motion of individual bodies. Wedge is moving towards left and block towards right. But the thing here to notice is center of mass of the system moves only vertically. 
If you are asking about how normal forces are created:
Normal forces are electromagnetic forces applied by the atoms/molecules on a surface of a rigid body to atoms/molecules on the other surface of another rigid body, that are in contact with each other and trying to pierce through each other. For example when we sit on ground, gravity pulls us down but the molecules of ground push the molecules of our body so that we don't penetrate in the ground and that's why ground feels rigid. Normal Contact Force is a repulsive force that acts when rigid bodies try to pierce each other. 
In the case of wedge + block, block wants to move vertically down but there is an obstacle and that is wedge which won't let it fall exactly vertically otherwise it will pierce through the surface of wedge so when the molecules of block come close to the molecules of wedge they start repelling each other and this repulsion is an external force to both block and wedge so they move in horizontal direction also. 
Now we come to the answer why normal $N$ is not equal to $mgcos\theta$ because if this would be the case then block will have a net force only $mgsin\theta$ and so block will move only in a direction which is tilted at an angle $\theta$ with the ground but that is not the case. Block is moving in combination of two motions:
One is sliding on the surface of the and another is that block moving to the left along with the wedge so that it remains on the surface.
Now assume N as a variable and draw the FBDs of the block and assume acceleration of wedge as $a_h$ to the left and acceleration of block as ($a_h$ to the left + $a_s$ along the direction of wedge surface which is tilted along a direction $\theta $ from the ground). For the block break acceleration correctly in the direction of parallel and perpendicular to the plane of surface of wedge and use $F_{ext} = ma$ for both block in 2 perpendicular directions one perpendicular to wedge surface and one parallel to wedge surface and for wedge in horizontal direction.

Yellow one is $a_h cos\theta$ and blue one is $a_h sin\theta$
