When a user login fails, is it possible to say "Password incorrect" or "Username does not exist" instead of the default message?
This message is set in user.module in the user_login_final_validate() function.  It's set as a bog-standard form_set_error() so can't really be over-ridden.  Looking at it, it also doesn't differentiate between whether or not the username or password is incorrect, so you wouldn't really be able to do anything useful.

As Clive mentioned, it's much better practice to keep a degree of ambiguity in certain error messages, and seeing as how this isn't wrapped in any kind of theme function and doesn't have separate behaviours for whether the username exists or password was incorrect, you're probably better off leaving it as is.

One last option you have is to user a hook_form_alter() on user_form to set an extra validation callback, and then check for the user name yourself.

Example:

(I can't remember the $form_state for the user form, so you'll have to die() or dpm() that yourself)

function mymodule_check_username_exists($form, &amp;$form_state){
  $user_exists = user_load_by_name($form_state['name']);

  if ($user_exists == FALSE ) {
   form_set_error('name', t('This username does not exist'));
  }
}