Generally speaking, hitting the DOM repeatedly is much slower than say swapping out a big block of HTML with innerHTML. I believe there are two reasons for this. One is reflow. The browser has to recalc for potential layout impact across potentially wide variety of elements. The other, I believe, and somebody correct me if I'm wrong, is that there's a bit of overhead involved in translating the stuff going on at the browser's post-compiled execution environment where rendering and layout state is being handled into an object you can use in JavaScript. Since the DOM is often under constantly changing conditions you have to run through the process every time with few opportunities to cache results of any kind, possibly to a degree even if you're just creating new elements without appending them (since you're likely to going to want pre-process CSS rules and things like what 'mode' the browser is in due to doctype, etc, that can be applied in a general context beforehand).
DOM methods allow you construct document fragments and create and append HTML element to those without affecting the actual document layout, which helps you avoid unnecessary reflow.
But here's where it gets weird.
Inserting new HTML into a node with nothing in it - close to a tie or something innerHTML is typically much faster at in a lot of (mostly older) browsers
Replacing a ton of HTML contents - this is actually something where DOM methods tend to win out when performance isn't too close to call.
Basically, innerHTML, if it stinks, tends to stink at the teardown process where large swaps are happening. DOM methods are better at teardown but tend to be slower at creating new HTML and injecting directly without replacing anything when there's any significant difference at all.
There are actually hybrid methods out there that can do pretty marvelous things for performance when you have the need. I used one over a year ago and was pretty impressed by response time improvement for swapping large swathes of HTML content for a lazy-loading grid vs. just using innerHTML alone. I wish I could find a link to the guy who deserves credit for figuring this out and spelling it out on the web (author, has written a lot of RegEx stuff too - couldn't google for the life of me).
As a matter of style vs perf, I think you should avoid tweaking the actual DOM node structure repeatedly but constructing HTML in a document fragment beforehand vs. using innerHTML is pretty much a matter of judgement. I personally like innerHTML for the most part because JS has a lot of powerful string methods that can rapidly convert data to HTML-ready strings. For instance:
var htmlStr = '<ul><li>' + arrayOfNames.join('</li><li>') + '</li></ul>';
That one-liner is a UL I can assign directly to innerHTML. It's almost as easy to build complete tables with the right data structure and a simple while loop. Now go build the same UL with as many LIs as the length of the arrayOfNames with the DOM API. I really can't think of a lot of good reasons to do that to yourself. innerHTML became de facto standard for a reason before it was finally adopted into the HTML 5 spec. It might not fit the node-based htmlElement object tweaking approach of the DOM API but it's powerful and helps you keep code concise and legible. What I would not likely do, however, is use innerHTML to edit and replace existing content. It's much safer to work from data, build, and swap in new HTML than it is to refer to old HTML and then start parsing innerHTML strings for attributes, etc when you have DOM manipulation methods convenient and ready for that.
Your chief performance concern should probably be to avoid hammering away at the 'live' portions of the DOM, but the rest I would leave up to people as a matter of style and testing where HTML generation is concerned. innerHTML is and has for years now been in the HTML5 working draft, however, and it is pretty consistent across modern browsers. It's also been de facto spec for years before that and was perfectly viable as an option since before Chrome was new, IMO but that's a debate that's mostly done at this point.