Update 2020-06-21 (ES6):
Given that jQuery has become somewhat unfashionable in the JavaScript world and that ES6 provides some nice syntactic sugar, I have written a pure JS equivalent to the original answer:
document.addEventListener('DOMContentLoaded', function() {
  const inputs = Array.from(
    document.querySelectorAll('input[name=telephone], input[name=mobile]')
  );
  const inputListener = e => {
    inputs
      .filter(i => i !== e.target)
      .forEach(i => (i.required = !e.target.value.length));
  };
  inputs.forEach(i => i.addEventListener('input', inputListener));
});
<form method="post">
  Telephone:
  <input type="tel" name="telephone" value="" required>
  <br>Mobile:
  <input type="tel" name="mobile" value="" required>
  <br>
  <input type="submit" value="Submit">
</form>
 
 
This uses the input event on both inputs, and when one is not empty it sets the required property of the other input to false.
Original Answer (jQuery):
I played around with some ideas and now have a working solution for this problem using jQuery:
jQuery(function ($) {
    var $inputs = $('input[name=telephone],input[name=mobile]');
    $inputs.on('input', function () {
        // Set the required property of the other input to false if this input is not empty.
        $inputs.not(this).prop('required', !$(this).val().length);
    });
});
I've written a jQuery plugin wrapping the above JavaScript code so that it can be used on multiple groups of elements.