While customizing the product tile JS template, you can calculate the discount percentage and display a label. The details required to calculate this are available in the product_details variable.
if (product_details.sale_price != product_details.price)
{
var discount_amount = Math.round(((product_details.price - product_details.sale_price) / product_details.price) * 100);
var $discount = $('<span class="product-discount-percentage">').html(discount_amount + '% OFF');
$link.append($discount);
}