As I can see you are targeting Windows Phone 8.1 Silverlight, then answer to this question is still actual, as at MSDN"
Applies to: Windows Phone 8 and Windows Phone Silverlight 8.1 | Windows Phone OS 7.1
In Windows Phone 8, if you call Show in OnBackKeyPress(CancelEventArgs) or a handler for the BackKeyPress event, the app will exit.
The solution is also given at MSDN. Shortly - run your Messeagebox.Show on Dispatcher:
protected override void OnBackKeyPress(System.ComponentModel.CancelEventArgs e)
{
e.Cancel = true;
Deployment.Current.Dispatcher.BeginInvoke(() =>
{
MessageBoxResult mbr = MessageBox.Show("Are you sure you want to leave this page?", "Warning", MessageBoxButton.OKCancel);
if(mbr == MessageBoxResult.OK)
{ OK pressed }
else
{ Cancel pressed }
});
}