How does a constant power force reduce the velocity of a body as the force increases? I know that the instantaneous power of a body $P$ is related to Force applied $F$ and instantaneous velocity $v$ as
$$P=\vec{F}. \vec{v}$$
Now, for a force of constant Power, I can clearly see that as the force increases, the velocity of the body on which the force is applied would decrease. But how is that possible?
Because as force increases, acceleration of the body must increase and hence it's instantaneous velocity also must increase?
 A: It can help to write out $F=ma$, and substitute that in:
$$P=m\vec a \cdot \vec v$$
Where the $\cdot$ is the dot product in the power equation above.
As $P$ and $m$ are constants in this scenario, this shows there is a relationships between $\vec a$ and $\vec v$.  The value of one constrains the other.
If I may take this out of vector land, let's handle it in 1 dimension.  This means the dot product simplifies into staight forward multiplication.
$$P=mav$$
By looking in just one dimension for a moment, we see that this "constant power" constraint implies a relationship between $a$ and $v$.  In particular:
$$a=\frac{P}{mv}$$
What I believe is giving you trouble is the

Because as force increases, acceleration of the body must increase and hence it's instantaneous velocity also must increase?

Now this intuition would serve you well if the constant power was slowing the object down.  It would be easy to see that, as the object slows, the force increases, increasing the acceleration, further decreasing the velocity.  That should feel natural and without contradiction.
That same logic does work in the case where the object is being accelerated by the constant power.  However, we have to remember that in that situation, the force is decreasing over time, not increasing.  As such, while we can talk about "as the force increases," we have to remember that the direction time must travel to talk that way is backwards.  As such, any intuition about how the acceleration and velocity of the object interact is backwards as well.  So the logic you have holds, it just leads to confusion because we're approaching the scenario backwards while your intuition is trying to approach it forwards.
If you work out all the equations with that logic and math, the result is consistent.  However, if at any point you fall back on your intuition, there's a strong likelihood that your intuition will try to make sense of the situation forwards, and the confusion will billow forth.
A: Think of a car with an engine that can only provide a fixed, limited, amount  of power (work per second).  When the car reaches its maximum velocity the driving force from the engine matches the resistive forces.
From Work = Force x distance
$$W=Fd$$
dividing by time
$$P=Fv$$
This formula can be interpreted as follows:
If the velocity is high, the car travels far each second, the available driving force from the engine is reduced.  If the velocity is low, the available driving force is high (a car can have high acceleration when it first sets off).
Also, if the resistive forces are high, then the maximum velocity, that the engine is capable of achieving for the car, is low.  If the resistive forces are low, the maximum velocity that can be achieved is high.
A: Start with $P = \vec{F}\cdot\vec{v}$
Taking the time derivative $0 = \frac{dP}{dt} = \frac{d\vec{F}}{dt}\cdot\vec{v} + \vec{F}\cdot\frac{d\vec{v}}{dt}$
Substitute $\vec{F} = m\vec{a} = m\frac{d\vec{v}}{dt}$
To attain $0 = \frac{d\vec{F}}{dt}\cdot\vec{v} + \frac{F^{2}}{m}$
Now, $F^{2}/m$ is always positive, so we see that we need $\frac{d\vec{F}}{dt}\cdot\vec{v}$ to be negative.
This is easily attained as long as $\vec{v}$ and $\frac{d\vec{F}}{dt}$ are in opposite directions.
In general, our condition is satisfied if $\frac{d\vec{F}}{dt} = -\vec{v} \frac{F^{2}}{mv^{2}} + \vec{u}$ for any $\vec{u}$ so that $\vec{u}\cdot\vec{v}=0$.
For increasing force, it necessitates that our initial velocity is negative. The velocity will increase but the magnitude of the velocity will decrease.
For an example solution, let $mv(t) = C(t-b)^{a}$ so that $F(t) = Ca(t-b)^{a-1}$ and $\frac{dF}{dt} = Ca(a-1)(t-b)^{a-2}$ and then solve for $\frac{dF}{dt} = -\frac{F^{2}}{mv}$.
$Ca(a-1) = -\frac{C^{2}a^{2}}{C}$, $-a = (a-1)$, $a=1/2$
Hence, you can see that
$\frac{dF}{dt} = -\frac{C}{4}(t-b)^{-3/2}$
$F = \frac{C}{2}(t-b)^{-1/2}$
$mv = C(t-b)^{1/2}$
Is a solution with constant power $Fv$ and you can see the force-change-over-time (the jerk!) and velocity are opposite sign. When C is negative, this is the negative velocity and increasing force case required by the question.
A: Precisely: the potential added acceleration due the increase in force would have to be counterbalanced by a deceleration: that is,  a resistive force is required in your scenario. This is case also when $F$ remains constant : then $v$ is also a constant, meaning that a resistive force balances out $F$.
A: 
Now as a force of constant power, I can clearly see that as the force increases, the velocity of the body on which the force is applied would decrease.

This is just wrong.  Any force, even if it is decreasing rapidly, will act to increase the velocity of the object it is acting on. Only when the force becomes negative will the velocity decrease because now the force is acting in the opposite direction.
Hence your question:

How is this possible?

It isn't. Hence my question to you: what do you mean by a constant power force?
