(1) that's still not the correct sort order (á should come before à)

I've no idea, but this page indicates the opposite. You may have to create a custom sort to override the default if desired.

(2) I actually get a different "sorted" list when I run the same exact code. This is the problem that I have - it seems the sort algorithms ignore the tone marks.

Perhaps it has to do with normalization. I still get the same sort order when using it.

#!/usr/bin/env perl
use v5.14;
use warnings;
use utf8::all;
use Unicode::Collate::Locale;
use Unicode::Normalize;

my $Collator = Unicode::Collate::Locale->new(locale =>'vi');
my @unsorted = ('á', 'ả', 'ã', 'à', 'ậ', 'ă', 'ạ', 'ẫ', 'a', 'ẩ' );
@unsorted = map { NFD($_) } @unsorted;
my @sorted = $Collator->sort(@unsorted);

say NFC("unsorted\n@unsorted");
say NFC("sorted\n@sorted");