You need a logic level gate or it won't switch on. Look for the VGS(th) value, this should be about 2V. Yours is 3-5V, and it's fully open at about 10V.
In this circuit you also need a p-channel FET, and your part is an n-channel (use those for low side switching). The symbol in your schematic is also for an n-channel FET.
Note that for your p-channel FET it will switch on when the output of the gate is LOW (0V, or -5V VGS). So you will need a NOR instead of OR gate.
This way you will connect the Arduino's pin to 5V while it is still powered off. That's a bad idea, and it will kill the pin. Adding a 10k resistor there will protect the clamping diode from burning.
The switch also needs a pull-down resistor (on the side of the OR gate), to make sure the OR gate gets a LOW level signal when the switch is open.
This should do much better (sorry, no suggestions for suitable MOSFET here - do a search on this forum or Digikey):
While the switch is open and the Arduino is off, both inputs of the NOR are pulled low (pin 2 via R2 and R4, pin 3 via R5), and the output is high, switching off the MOSFET. R3 is to limit the current rushing in to charge the gate, protecting the NOR output (usually can not supply more than 10-20 mA, depending on the part).
When the switch closes, the Arduino is still off, but R2 limits the current through the clamping diode to <0.5 mA which is safe, especially as it lasts only a very short time: until the Arduino is powered up. The pin 2 of the NOR is pulled high, the output goes low, and the MOSFET is switched on.
Now you can set the Arduino pin "Arduino_power_signal" to high to keep the power on, even when the switch goes off.