Это легко оценить:
>>> from timeit import Timer
>>> ts = Timer("s.decode('utf-8')", "s = 'ééé'")
>>> ts.timeit()
8.9185450077056885
>>> tu = Timer("unicode(s, 'utf-8')", "s = 'ééé'")
>>> tu.timeit()
2.7656929492950439
>>>
Очевидно, unicode()
быстрее.
FWIW, я не знаю, откуда у вас впечатление, что методы будут быстрее - это совсем наоборот.