While a creature's paralyzed, it can't opt to fly from place to place even if its flight is magical and wingless

The Pathfinder Core Rulebook FAQ includes this exchange:

Question

Can a paralyzed or stunned creature keep flying with magical flight? Does a creature with magical flight not apply bonuses or penalties to Fly checks because it doesn’t have a “natural” fly speed? Does flying make a creature immune to being flat-footed?

Answer

No, any creature that loses all actions can’t take an action to attempt a Fly check to hover in place and thus automatically falls. That includes a paralyzed, stunned, or dazed creature. Magical flight doesn’t act any differently [from nonmagical flight], even for paralysis, as it [magical flight] isn’t a purely mental action. A creature with 0 Dexterity can’t fly, and paralysis sets a creature’s Dexterity to 0. Despite the fact that the Fly skill mentions that bonuses and penalties from maneuverability apply to creatures with natural fly speeds, they apply for any fly speed. If they didn’t apply to creatures that gained flight artificially or through magic, then those maneuverabilities (like the listed good maneuverability for the fly spell) would have no game effect. Finally, the statement “You are not considered flat-footed while flying” means that flying (unlike balancing using Acrobatics or climbing) doesn’t automatically make you flat-footed or force you to lose your Dexterity bonus to AC; it doesn’t mean that flying makes you immune to being caught flat-footed.

(Emphasis, link, and editorializing mine.) You can read a multpage thread that predates this 2015 ruling that debates this topic here.

Were the GM to make a house rule saying that the spell fly and other methods of magical wingless flight do allow a creature to jet from place to place by taking purely mental actions, the campaign would have to deal with the subsequent fallout from such a ruling. That is, any wingless creature that the DM rules flies by mental effort alone—and that'd probably be all the DM's applicable monsters—can now fly away despite being affected by a hold person effect, for example. For this GM, that would be bridge too far, and, while this player wouldn't abandon a campaign in which such a house rule was made, this player would urge the GM reconsider as—seriously—casters are already powerful enough! If unable to get the GM to reconsider, this player would find for his PC a means of such flight posthaste.

Yes, it applies to all movements

Unarmored Movement (PHB, 78) States:

Starting at 2nd level, your speed increases by 10 feet while you are not wearing armor or wielding a shield.

It does NOT qualify as your Walking Speed (or Swimming Speed, or Flying Speed)...just Speed. This applies to all types of movements and would add additional speed to the Fly spell as well.

This is supported by Jeremy Crawford as well.

Unarmored Movement is intended to increase a monk's innate speed, including an aarakocra monk's flying speed.

He further clarifies Bonuses and Penalties that apply to Speed in general:

Bonuses/penalties to speed apply to your speeds in general, unless the text specifies walking, flying, etc

As the Unarmored Movement does not specify a specific type of speed, it applies to all.

Fly Spell specifically

Fly states (PHB, 243)

The target gains a flying speed of 60 feet for the duration.

The implication here is that you (the target) had no Fly Speed (or a lower Fly Speed) before casting and it is now a speed that you, the target have. Once it becomes your speed, it becomes subject to Unarmored Movement.

Similar to Special Types of Movement in the PHB, page 182)

While climbing or swimming, each foot of movement costs 1 extra foot (2 extra feet in difficult terrain), unless a creature has a climbing or swimming speed.

Here, Swimming has a penalty, unless they have a Swimming Speed. Once they have that Speed, from whatever source, then Unarmored Movement should apply.

Rule of Cool

And it's fun! Monks are supposed to be super quick. Let them be super quick in all their speed!