業務でそんな感じの要件が出たので実装してみました。

1,2行で書けると思ったら案外面倒だった・・・
ライブラリはGuavaとlombokを使ってます。(残念ながら職場はJava7なのです）
もっといい方法がありそうな気がするけどとりあえず動いたのでメモ

コード

S3ObjectDelete.java

@RequiredArgsConstructor
public class S3ObjectDelete {
    private AmazonS3Client client = new AmazonS3Client();

    private final String bucket;

    public static void main(String[] args) {
        val hoge = new S3ObjectDelete("バケット名");
        hoge.delete("プレフィックス");
    }

    public void delete(String prefix) {
        // 同時に削除できる件数の上限が1000らしいので分割して処理
        for (val keys : Lists.partition(keys(prefix), 1000)) {
            String[] array = keys.toArray(new String[keys.size()]);
            client.deleteObjects(new DeleteObjectsRequest(bucket).withKeys(array));
        }
    }

    List<String> keys(String prefix) {
        ObjectListing objects = client.listObjects(bucket, prefix);
        val f = new S3Object2StringKey();
        List<String> keys = new ArrayList<>(Lists.transform(objects.getObjectSummaries(), f));

        // 一度に取得できる件数のデフォルトが1000件らしいのでループしてすべて取得
        while (objects.isTruncated()) {
            objects = client.listNextBatchOfObjects(objects);
            keys.addAll(Lists.transform(objects.getObjectSummaries(), f));
        }
        return keys;
    }
}

public static class S3Object2StringKey implements Function<S3ObjectSummary, String> {
    @Override
    public String apply(S3ObjectSummary input) {
        return input.getKey();
    }
}

追記

AmazonS3Clientは非推奨となり
AmazonS3ClientBuilderを使うことを推奨しているようです
この記事などが参考になりました