Recently, I reset my Windows 10 Surface Pro 4 and in Microsoft Edge browser, noticed there is no “Add New” option in search engine.
You can go to your search engines by clicking “…” in the top right corner of Edge -> Settings -> Advanced Settings -> Search in the address bar with option and click on the Change button. See below.
If this is the first time you are using Edge, you will not see "Add new" option or any other search engines.
The way, Edge works is, it discovered search engines when you visit a search engine website. To see Google in your search engines list, you need to visit Google.com.
Type and open Google.com in Edge.
Now, go back to the Advanced Settings of Edge, you will see Google in the search engines listing now.
Click on Google Search (discovered), select it and Set as default.