Drupal - How to decide between module_exists and function_exists?

You should always program to the API and not the implementation. If Drupal provides a mechanism to do something, use it.

module_exists() should almost always be used for soft dependencies on something provided by a Drupal module. You can always get version info, and decide what to do, using system_get_info(). There have been cases where functions are available when modules have been disabled (some of the class autoloader modules have has this problem).

function_exists() should be reserved for checking whether a PHP feature or library is available. Core has some examples of this in some of the drupal_ wrappers for string manipulation and character set conversion.

module_exists is a Drupal API function used to determine whether a module is installed, it isn't designed to give any guarantees of the functionality a module might contain, including what functions it declares.

function_exists is a PHP core function which literally determines whether a function with a given name exists in the current request.

As such, they aren't really comparable with one another, you use them for different things. In fact it would be easy, albeit potentially redundant, for them to complement one another, e.g.

// Do something with a specific module 
if (module_exists('foo')) {
  // Check what's available 
  if (function_exists('foo_bar')) {
    // ...
  }
  elseif (function_exists('foo_baz')) {
    // ...
  }
}

You are right, function_exists is a more robust way to check the existence of the API function provided by contrib module. It is very suitable for directly using the contrib module's API.

I use Session Cache API as an example:

if (function_exists('session_cache_set')) {
  session_cache_set($bin, $data)
}

However, some contrib modules only provides some extra properties or feature, it is very hard to say which dependent function is. In this case, you need to use module_exists

I use Elements as an example:

if (module_exists('elements')) {
  $form['url'] = array(
    '#type' => 'urlfield',
    // other code
  );
}
else {
  $form['url'] = array(
    '#type' => 'textfield',
    // other code
  );
}