I, too, was wondering whether is_callable or function exists is faster when checking class methods. So, I setup the following test:
<?php
function doTimes($start, $end)
 {
 $start_time = explode (" ", $start);
 $start_time = $start_time[1] + $start_time[0];
 $end_time = explode (" ", $end);
 $end_time = $end_time[1] + $end_time[0];
 $time = $end_time - $start_time;
 return $time;
 }
class test
 {
 function test()
 {
 return true;
 }
 }
 
$callableIsTrue = false;
$startIsCallable = microtime();
for($i = 0; $i < 10000; $i++)
 {
 if(is_callable(array('test', 'test'))) { $callableIsTrue = true; }
 }
$endIsCallable = microtime();
$existsIsTrue = false;
$startExists = microtime();
for($i = 0; $i < 10000; $i++)
 {
 if(function_exists('test::test')) { $existsIsTrue = true; }
 }
$endExists = microtime();
$timeIsCallable = doTimes($startIsCallable, $endIsCallable);
$timeExists = doTimes($startExists, $endExists);
echo "<b>is_callable = ".($callableIsTrue ? "TRUE" : "FALSE")."</b>, \n";
echo "<b>function_exists = ".($existsIsTrue ? "TRUE" : "FALSE")."</b><br>\n";
echo "<br>Did 10000 is_callables in ".$timeIsCallable." seconds";
echo "<br>Did 10000 function_exists in ".$timeExists." seconds";
?>

This gives the output :
is_callable = TRUE, function_exists = FALSE
Did 10000 is_callables in 0.0640790462494 seconds
Did 10000 function_exists in 0.0304429531097 seconds
So the fact that function_exists is twice as fast is slightly over shadowed by the fact that it doesn't work on class methods, at least not as far as I can tell.