Yes, you're not seeing it because you need iOS 16.
Also, if I'm understanding your post correctly, 'Add New Wallpaper' doesn't quite mean what you think it means. It's not used to add additional wallpaper to the existing stock gallery to pick from later. It's used to create a new Lock Screen & Home Screen wallpaper set. With iOS 16, you can have multiple wallpaper sets to switch between from the Lock Screen (as mentioned in the bottom part of that screenshot).
If you want to create your own gallery of wallpaper to browse and pick from, the best thing you can do is to create an album(s) in Photos to organize them. The albums should show up in Settings -> Wallpaper -> Choose a New Wallpaper when using iOS 15 or older.