The big question is circuit load. You can experiment by finding the breaker that powers the outlet you mention behind the stove and see how many other outlets are powered from that one breaker. Also read the breaker's rating. The microwave is 1000W, or 8 to 9 amps. What else is on the breaker? Read their labels to add up current. I'm not clear whether you still have the exhaust hood working or not. As a general rule you try to have the maximum sustained load on a circuit not exceed 80% of the breaker's rating, although strictly speaking it is safe up to 100%. The new short piece of cable you will need is the kind used for normal in-the-wall household wiring, probably type NMD-7. If the breaker is 15 amp, get 14/2 gauge (14 gauge, 2 current-carrying (white and black) wires, one bare Ground lead); if the breaker is 20 amp, get 12/2.
What you proposed originally is NOT acceptable from a code standpoint, because it's not really safe, either. Do as Fiat1 suggests - install a proper device box, duplex receptacle and cover. Actually, a box that can mount IN the wall, in a suitable hole of the right size, may be preferred. The electrical / hardware store will have several types, so get them to explain how to use the right one for your job. BUT to get power to that box you need cable and it SHOULD NOT be exposed. It should run inside the wall. So, try to arrange that the box for the microwave is inside the space behind it (above the new shelf) and pretty much directly above the existing box behind the stove. That way it is likely (not guaranteed) that you can open up a hole behind the box, drop a length of cable down (end bared a little, with a loop of wire on the end to snag), and fish around from the lower box to pull it to that box. FIRST, SHUT OFF THE BREAKER AND TEST TO BE SURE IT'S OFF! You will have to temporarily remove the duplex outlet in the lower box and probably should loosen or temporarily remove the clamp mechanism inside it that holds the existing cable in place so that you can use the existing hole (or open a new one) in the box to poke a hooked wire through for fishing the new cable end. Pull the end of the new cable into the lower box along with the old cable. Bare off about 12" of outer sheath on the new cable, then snip off about 6" from the three wires it contains and save them. Now you need to splice the wires together and create some short leads to feed the outlet in the lower box.
For this you'll need two wire splicing devices. The common type are plastic screw-on things by Marrette. Bare the ends of the new cable's white and black wires about ½". Do the same for BOTH ends of the short extra pieces you cut off. Now take the WHITE wires of the two cables (old and new) PLUS the WHITE short piece, put the three ends together and twist on the Marrette connector. Do the same for the BACK wires. The old cable will have a bare Ground lead fastened to a screw in the back of the metal box. Unscrew it and pull it partly out. Twist it tightly with the new cable's bare Ground wire and screw the combined bare wires back to the back of the box. This should leave you with a lone bare lead (if you have two, snip one off) long enough to reach out to the green Ground terminal of the old duplex receptacle. Fasten that on. Re-install the cable clamp piece at the back of the box where the two cables enter, so that it clamps down on the INSULATED OUTER JACKET of each cable and holds it firmly. Now take the receptacle and turn it so, of the three holes in each half, the round GROUND one is at the bottom of the triangle, and the two straight-blade ones are above it. In that orientation as you look at it from the front (as if it were already in the wall), the LEFT side with the wider blade slot is Neutral - fasten the WHITE lead there. Its screw should be silvery. Then fasten the BLACK lead to the right-hand side with the brass screw. Now bend and fold the wires so that you can reposition the duplex outlet in the box and screw it back into place, then replace the box cover.
You just tapped into the existing circuit. Now you have a cable coming out of the hole in the wall where you will mount the new outlet box. Besides the box itself you will need some sort of cable clamp mounted in a knock-out hole in the box. The cable is fed through that so that the clamp can grab onto the outer covering of the cable and mechanically anchor it to the box at the entry point. But before you fit it together, estimate where the clamping point will be and cut the cable about 8" longer than that, then remove the outer covering from those 8". THEN feed it through the clamp, tighten the clamp, and mount the box on or in the wall.
First electrical connection is to loosen one of the screws in the back of the box, wrap the bare Ground lead around it and tighten. Connect its end to the green Ground terminal of the new receptacle. Now snip about 2" off the ends of each of the white and black leads and bare about ½" of the ends. Turn the receptacle round-hole-down, connect WHITE to LEFT (wide slot, silvery screw) and BLACK to RIGHT on it. Tuck the wires in behind and push the receptacle into the box so you can tighten its mounting screws, then install the cover plate. Now you can turn the breaker back on and use it.