It can take a while, but the longest I've heard is 90 minutes. You can just start again as they can sometimes freeze during this process, the official instructions are:
If your phone is on, turn it off.
Press and hold the Volume Down and Volume Up buttons, and then press and hold the Power button at the same time until the phone turns on. You'll see the word "Start" with an arrow around it.
Press the Volume Down button twice to highlight "Recovery mode".
Press the Power button to start Recovery mode. You'll see an image of an Android robot with a red exclamation mark and the words "No command".
While holding the Power button, press the Volume Up button.
Use the volume buttons to scroll to "wipe data/factory reset" and press the Power button to select it.
Scroll down to "Yes - erase all user data" and press the Power button to select it.
Note: If your phone becomes unresponsive at any point during these steps, you can restart it by holding down the Power button for several seconds.