FILENAME_PRODUCTS_ALL is defined in includes/filenames.php - that won't help you.
PRODUCT_NEW_LIST_DATE_ADDED is a database configuration key as I described above - it's value is used to determin if the date added column is displayed at all, and if so, in which order. Again, that won't help you achieve what you want.
If you take a look at includes/templates/template_default/templates/tpl_modules_products_new_listing.php at line 61 you'll see this code:
Code:
$display_products_date_added = TEXT_DATE_ADDED . ' ' . zen_date_long($products_new->fields['products_date_added']) . str_repeat('<br clear="all" />', substr(PRODUCT_NEW_LIST_DATE_ADDED, 3, 1));
You can see there that the database outpur for the field products_date_added is being used by the function zen_date_long() to format it for display. So where you need to be looking is at that function.
Plug that function name into the search field for functions in the Developers Tool Kit, search All Files - Catalog and you'll find it's contained in includes/functions/functions_general.php at line 189.