I use a mixture of Behind the Name, talking to people from the culture I want a suitable name for a character from, homages to people I know or famous people and... just making crap up.
So in my comic I have:
Lune - named for the river Lune in Lancashire.
Talwar - asked my punjabi partner for suggestions, one of them was Talwar, which is a type of sword, so an irresistible choice.
Ellis - comics fans probably know that the fictional president in the X-men series is called Ellis. There's also a famous comics writer called Warren Ellis.
Aoki - I liked the idea of using a surname with the kanji for "blue" for a character whose theme colour is blue (I know, it's a bit on the nose, but my comic is a bit silly so...). Also the local supermarket when I was a student in Japan was Aoki Super, so it's kind of a silly nod to my days at Nagoya Gaidai.
In more classic fantasy, I'll often just mash two words together for things like "Dragonsbane", "Oldriver", "Frostwell" etc. It works well because a lot of real surnames originated like this. Shepard comes from Sheepherd, for example. Most people's surnames come from some kind of description of what their ancestor looked like "Short", "Blacklock" (black locks of hair), what they did "Turner" (wood turner), "Smith", or where they lived; "Lancaster", "Granger" (lived on a grange).