In 'Recent searches' click on 'delete all' (trash bin) icon - all entires will be deleted after confirmation in pop-up.
The 'Recent searches' label is still displayed.
This is a regression from 4.1.7(171) - clearing 'Recent searches' will also prevent the label from displaying.