Figured this one out, but it's a bit of a hack.
Open the Photos app.
Go to the "Albums" tab.
Press "Edit" and delete all of your custom albums (if you have any). All photos will be deleted within, so it's quick win.
Go into your "Camera Roll". You should be at the bottom, most recent picture.
Press "Select" and begin drag-selecting from the most recent picture upwards.
Now, the hack: Without releasing your selection drag, tap the title bar to cause the album to scroll to the top. Your selection should follow.
Press "Delete" and confirm the number of deletions
Wait - it takes a while even for only 2000.