Data structure/aglorithm for strings to see if there exists two strings you can concatenate to get a target?
Store the strings in a trie.  Build a second trie that stores the reverse of the strings.  Now you can quickly check whether the target string T is a concatenation of some pair of strings: start walking the first trie, using the left-most characters of T (walking left to right), and simultaneously start walking the second trie, using the right-most characters of T (walking right to left).  By walking the first trie, you find all prefixes of T that are in the dataset; by walking the second trie, you find all suffices of T that are in the dataset; and then you can look for a pair of a prefix and a suffix of the right length to cover all of T (without overlap).

Your approach of storing the strings in sorted order is also reasonable, but you'll need two sorted arrays: one to store the strings; another to store the reverse of the strings.  Given a target string T of length n, for each i, you look up T[1..i] in the first sorted array (using binary search) and look up reverse(T[i+1..n]) in the second sorted array (using binary search).  As an optimization, start each binary search from where the previous search left off (i.e., once you've found T[1..i] in the first sorted array, that helps you find T[1..i+1]; you shouldn't need to start over from scratch.)

So yeah, your idea based on sorted arrays works too, though two tries might be somewhat more efficient.